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

Question

我想使用字符 ASCII 码压缩字符串。我想使用数字模式压缩它们。因为ASCII码是数字，所以我想在ASCII字符码列表中找到子模式。

理论

这将是我找到的每个模式的格式：

[nnn][n][nn]，其中：
- [nnn] 是第一个字符的 ASCII 码，来自具有相同模式的组号。
- [n]是某个pattern/rule的自定义号码（下面我会详细解释）。
- [nn] 显示此规则发生的次数。

数字模式没有具体建立。但是让我举几个例子：

相同的字符
线性增长（每一个 number/ascii 都比前一个更大）
线性减少（每个number/ascii都比以前小，有一个）

现在让我们看看一些情况：

“adeflk”变为“097.1.01-100.2.03-108.3.02”
- 相同的字符，线性增长三倍，线性下降两倍。
“rrrrrrrrrrrr”变成“114.1.11”
- 11 次相同的字符。
“tsrqpozh”变为“116.3.06-122.1.01-104.1.01”
- 线性减少六倍，相同的字符，相同的字符。

我添加了点 ('.') 和破折号 ('-')，以便您可以轻松看到它们。

的确，我们没有看到好的结果（压缩）。我想将此算法用于大字符串。并添加更多规则（数字模式），我们增加更改以使结果比原始结果更短。我知道现有的压缩解决方案。我想要这个解决方案，因为结果只有数字，它对我有帮助。

我试过的

// recursive function
function run (string $data, array &$rules): string {
    if (strlen($data) == 1) {
        // str_pad for having always ASCII code with 3 digits
        return (str_pad(ord($data), 3, '0', STR_PAD_LEFT) .'.'. '1' .'.'. '01');
    }

    $ord = ord($data); // first char
    $strlen = strlen($data);
    $nr = str_pad($ord, 3, '0', STR_PAD_LEFT); // str_pad for having always ASCII code with 3 digits
    $result = '';

    // compares every rule
    foreach ($rules as $key => $rule) {
        for ($i = 1; $i < $strlen; $i++) {
            // check for how many times this rule matches
            if (!$rule($ord, $data, $i)) {
                // save the shortest result (so we can compress)
                if (strlen($r = ($nr .'.'. $key .'.'. $i .' - '. run(substr($data, $i), $rules))) < strlen($result)
                || !$result) {
                    $result = $r;
                }
                continue 2; // we are going to next rule
            }
        }

        // if comes here, it means entire $data follow this rule ($key)
        if (strlen($r = (($nr .'.'. $key .'.'. $i))) < strlen($result)
        || !$result) {
            $result = $r; // entire data follow this $rule
        }
    }

    return $result; // it will return the shortest result it got
}

// ASCII compressor
function compress (string $data): string {
    $rules = array( // ASCII rules
        1 => function (int $ord, string $data, int $i): bool { // same char
            return ($ord == ord($data[$i]));
        },
        2 => function (int $ord, string $data, int $i): bool { // linear growth
            return (($ord+$i) == ord($data[$i]));
        },
        3 => function (int $ord, string $data, int $i): bool { // progressive growth
            return ((ord($data[$i-1])+$i) == ord($data[$i]));
        },
        4 => function (int $ord, string $data, int $i): bool { // linear decrease
            return (($ord-$i) == ord($data[$i]));
        },
        5 => function (int $ord, string $data, int $i): bool { // progressive decrease
            return ((ord($data[$i-1])-$i) == ord($data[$i]));
        }
    );

    // we use base64_encode because we want only ASCII chars
    return run(base64_encode($data), $rules);
}

我添加点 ('.') 和破折号 ('-') 只是为了方便测试。

结果

compress("ana ar") => "089.1.1 - 087.1.1 - 053.1.1 - 104.1.1 - 073.1.1 - 071.4.2 - 121.1.01"

没关系。而且运行速度很快。没问题。

compress("ana aros") => Fatal error: Maximum execution time of 15 seconds exceeded

如果字符串有点长，它就会变得太多。它可以快速正常地处理 1-7 个字符。但是当字符串中有更多字符时，就会发生这种情况。

该算法确实运行不完美，也不 return 完美的 6 位数模式。在到达那里之前，我一直坚持下去。

问题

我如何才能提高回溯的性能运行现在还可以使用更多规则？

Answer 1

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

你永远不会得到只有一个字母的序列，因为每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');

Answer 2

搜索梯度/中缀重复不适合压缩自然语言。使用基于字典的方法压缩自然语言要容易得多（与压缩数据捆绑在一起的动态字典，以及在参考集上训练的预编译字典），因为即使是 ASCII 编码中的重复序列通常也不遵循任何琐碎的几何图案，但仅观察单个字符的序数表示时显得相当随机。

就是说，您的算法之所以如此缓慢，是因为您正在探索所有可能的模式，这导致输入长度呈运行时间指数，恰好 O(5^n)。为了在一组 5 arbitrary 规则中找到 ideal 压缩的自我设定目标，那是已经尽可能好了。如果有的话，您只能将运行时间复杂度降低一个常数因子，但您无法摆脱指数运行时间。换句话说，即使您应用了完美的优化，也只会使您可以处理的最大输入长度增加 30-50%，然后您不可避免地会再次运行超时。

@noam 的解决方案甚至没有尝试找到 ideal 模式，而是简单地贪婪地使用第一个匹配模式来消耗输入。因此它会错误地忽略更好的匹配，但在 return 中它也只需要查看每个输入字符一次，导致线性运行时间复杂度 O(n).

当然，您当前的解决方案中有一些细节使得解决起来更容易，只是基于对您的规则的简单观察。请注意，当您尝试添加更多规则时，这些假设会被打破。

具体来说，如果您对尝试规则的顺序很明智，则可以避免大部分回溯：

尝试先开始一个新的几何图案ord(n[i])=ord(n[0])+i，只有匹配至少前面3个字符时才接受为匹配项.
尝试继续当前的几何图案。
尝试继续当前的渐变模式。
尝试开始新的渐变ord(n[i])=ord(n[0])+i，并且仅当它与前面至少2个字符匹配时才接受为匹配项。
尝试最后开始/继续简单重复，并始终接受。

一旦输入的字符被这些规则中的任何一个接受（意味着它已被序列使用），您将不再需要从它回溯或检查任何其他规则，因为您已经找到了最好的表现形式。您仍然需要重新检查添加到序列中的每个后续字符的规则，因为可能需要将渐变规则的后缀作为几何规则的前缀。

一般来说，您的规则集中允许这样做的模式是这样的事实，即对于每个具有更高优先级的规则，该规则的匹配项都不会在任何后续规则中有更好的匹配项。如果你愿意，你可以很容易地正式证明你在你的集合中的每一对可能的规则。

如果您想测试您的实现，您应该专门测试 ABDHIK 等模式。尽管H匹配当前运行ning个几何序列ABDH，但以它作为新几何序列HIK的起点无条件是更好的选择。

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

Compressing string using ASCII char codes using backtracking in php

php

compression

recursion

ascii

backtracking

理论

我试过的

结果

问题