在 php 中使用回溯使用 ASCII 字符代码压缩字符串

Question

我想可以使用 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倍。“rrrrrrrrrrrr”变为“114.1.11”相同的字符十一次。“tsrqpozh”变为“116.3.06-122.1.01-104.1.01”线性减少六次，相同的字符，相同的字符。我添加了点（“.”）和破折号（“-”），以便您可以轻松看到它们。事实上，我们没有看到好的结果（压缩）。我想将此算法用于大字符串。并添加更多规则（数字模式），我们增加了更改以使结果比原始结果更短。我知道现有的压缩解决方案。我想要这个解决方案，因为结果只有数字，它对我有帮助。

Answer 1

搜索渐变/中缀重复并不适合压缩自然语言。使用基于字典的方法压缩自然语言要容易得多（与压缩数据捆绑在一起的动态字典，以及在参考集上训练的预编译字典），因为即使是 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无疑是更好的选择。

Answer 2

我对你的问题提出了一个初步的解决方案。请注意：

• 你永远不会得到只有一个字母的序列，因为每两个连续的字母都是具有一定差异的“线性增长”。

• 我的解决方案不是很干净。例如，您可以将$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');