我想可以使用 chars ASCII 代碼來壓縮字符串。我想使用數字模式來壓縮它們。因為 ASCII 代碼是數字，所以我想在 ASCII 字符代碼列表中查找子模式。理論這將是我找到的每個模式的格式：[nnn][n][nn]，其中：[nnn] 是第一個字符的 ASCII 代碼，來自具有相同模式的組編號。[n] 是特定模式/規則的自定義編號（我將在下面解釋更多）。[nn] 顯示此規則發生的次數。數字模式沒有具體確定。但讓我舉一些例子：相同的字符線性增長（每個數字/ascii 都比以前大，其中一個）線性減少（每個數字/ascii 都比以前小，其中一個）現在讓我們看看一些情況：“adeflk”變為“097.1.01-100.2.03-108.3.02”相同的字符，線性增長3倍，線性下降2倍?！皉rrrrrrrrrrr”變為“114.1.11”相同的字符十一次?！皌srqpozh”變為“116.3.06-122.1.01-104.1.01”線性減少六次，相同的字符，相同的字符。我添加了點（“.”）和破折號（“-”），以便您可以輕松看到它們。事實上，我們沒有看到好的結果（壓縮）。我想將此算法用于大字符串。并添加更多規則（數字模式），我們增加了更改以使結果比原始結果更短。我知道現有的壓縮解決方案。我想要這個解決方案，因為結果只有數字，它對我有幫助。
2 回答
白豬掌柜的
TA貢獻1893條經驗 獲得超10個贊
搜索漸變/中綴重復并不適合壓縮自然語言。使用基于字典的方法壓縮自然語言要容易得多（與壓縮數據捆綁在一起的動態字典，以及在參考集上訓練的預編譯字典），因為即使是 ASCII 編碼中的重復序列通常也不遵循任何規則。微不足道的幾何圖案，但當僅觀察單個字符的序數表示時，顯得相當隨機。
也就是說，您的算法如此慢的原因是因為您正在探索所有可能的模式，這會導致輸入長度的運行時間呈指數增長，準確地說是O(5^n)。對于您自己設定的在一組 5 個任意規則中找到理想壓縮的目標來說，這已經是盡可能好的了。如果有的話，您只能將運行時間復雜度降低一個常數因子，但無法擺脫指數運行時間。換句話說，即使您應用了完美的優化，也只會將您可以處理的最大輸入長度增加 30-50%，然后您就不可避免地會再次遇到超時。
@noam 的解決方案甚至不嘗試找到理想的模式，而只是貪婪地使用第一個匹配模式來消耗輸入。因此，它會錯誤地忽略更好的匹配，但作為回報，它也只需查看每個輸入字符一次，從而導致線性運行時間復雜度O(n)。
當然，您當前的解決方案中有一些細節使得解決起來更加容易，只需基于對規則的簡單觀察即可。但請注意，當您嘗試添加更多規則時，這些假設將會被打破。
具體來說，如果您明智地選擇嘗試規則的順序，則可以避免大部分回溯：
首先嘗試開始一個新的幾何圖案，并且僅當它與前面至少3個字符
ord(n[i])=ord(n[0])+i匹配時才接受為匹配。嘗試延續當前的幾何圖案。
嘗試繼續當前的漸變模式。
嘗試開始新的漸變，并且僅當它與前面至少 2 個字符
ord(n[i])=ord(n[0])+i匹配時才接受匹配。嘗試最后開始/繼續簡單的重復，并始終接受。
一旦輸入中的字符被任何這些規則接受（意味著它已被序列消耗），您將不再需要從它回溯或檢查它的任何其他規則，因為您已經找到了最佳的表示形式它。您仍然需要重新檢查添加到序列中的每個后續字符的規則，因為可能需要漸變規則的后綴作為幾何規則的前綴。
一般來說，規則集中允許這樣做的模式是這樣的事實：對于具有較高優先級的每個規則，該規則的匹配項不能在任何后續規則中具有更好的匹配項。如果您愿意，您可以輕松地為您的集合中的每對可能規則進行正式證明。
如果您想測試您的實現，您應該專門測試諸如ABDHIK. 即使與H當前運行的幾何數列相匹配ABDH，但將其作為新的幾何數列的起點HIK無疑是更好的選擇。
慕虎7371278
TA貢獻1802條經驗 獲得超4個贊
我對你的問題提出了一個初步的解決方案。請注意：
你永遠不會得到只有一個字母的序列，因為每兩個連續的字母都是具有一定差異的“線性增長”。
我的解決方案不是很干凈。例如，您可以將
$matches和組合$rules到一個數組中。我的解決方案是幼稚和貪婪的。例如，在示例中
adeflk，序列def是 3 的序列，但因為我的解決方案是貪婪的，所以它會考慮ad作為 2 的序列，并ef作為另一個 2 的序列。話雖如此，您仍然可以改進我的代碼。該代碼很難測試。您可能應該使用 OOP 并將代碼劃分為許多易于單獨測試的小方法。
<?php
function compress($string, $rules, $matches) {
if ($string === '') {
return getBestMatch($matches);
}
$currentCharacter = $string[0];
$matchFound = false;
foreach ($rules as $index => &$rule) {
if ($rule['active']) {
$soFarLength = strlen($matches[$index]);
if ($soFarLength === 0) {
$matchFound = true;
$matches[$index] = $currentCharacter;
} elseif ($rule['callback']($currentCharacter, $matches[$index])) {
$matches[$index] .= $currentCharacter;
$matchFound = true;
} else {
$rule['active'] = false;
}
}
}
if ($matchFound) {
return compress(substr($string, 1), $rules, $matches);
} else {
return getBestMatch($matches) . startNewSequence($string);
}
}
function getBestMatch($matches) {
$rule = -1;
$length = -1;
foreach ($matches as $index => $match) {
if (strlen($match) > $length) {
$length = strlen($match);
$rule = $index;
}
}
if ($length <= 0) {
return '';
}
return ord($matches[$rule][0]) . '.' . $rule . '.' . $length . "\n";
}
function startNewSequence($string) {
$rules = [
// rule number 1 - all characters are the same
1 => [
'active' => true,
'callback' => function ($a, $b) {
return $a === substr($b, -1);
}
],
// rule number 2 - ASCII code of current letter is one more than the last letter ("linear growth")
2 => [
'active' => true,
'callback' => function ($a, $b) {
return ord($a) === (1 + ord(substr($b, -1)));
}
],
// rule number 3 - ASCII code is a geometric progression. The ord() of each character increases with each step.
3 => [
'active' => true,
'callback' => function ($a, $b) {
if (strlen($b) == 1) {
return ord($a) > ord($b);
}
$lastCharOrd = ord(substr($b, -1));
$oneBeforeLastCharOrd = ord(substr($b, -2, 1));
$lastDiff = $lastCharOrd - $oneBeforeLastCharOrd;
$currentOrd = ord($a);
return ($currentOrd - $lastCharOrd) === ($lastDiff + 1);
}
],
// rule number 4 - ASCII code of current letter is one less than the last letter ("linear decrease")
4 => [
'active' => true,
'callback' => function ($a, $b) {
return ord($a) === (ord(substr($b, -1)) - 1);
}
],
// rule number 5 - ASCII code is a negative geometric progression. The ord() of each character decreases by one
// with each step.
5 => [
'active' => true,
'callback' => function ($a, $b) {
if (strlen($b) == 1) {
return ord($a) < ord($b);
}
$lastCharOrd = ord(substr($b, -1));
$oneBeforeLastCharOrd = ord(substr($b, -2, 1));
$lastDiff = $lastCharOrd - $oneBeforeLastCharOrd;
$currentOrd = ord($a);
return ($currentOrd - $lastCharOrd) === ($lastDiff - 1);
}
],
];
$matches = [
1 => '',
2 => '',
3 => '',
4 => '',
5 => '',
];
return compress($string, $rules, $matches);
}
echo startNewSequence('tsrqpozh');
- 2 回答
- 0 關注
- 169 瀏覽
添加回答
舉報
0/150
提交
取消