algorithm - 给定原始字符串和编码字符串，如何归纳编码？

Question

假设我有一个原始字符串和一个编码字符串，如下所示:

"abcd"-> "0010111111001010"，那么一种可能的解决方案是"a"匹配"0010"，"b"匹配"1111"，"c"匹配"1100"，"d"匹配用“1010”。

如何编写一个程序，给定这两个字符串，并找出可能的编码规则？

我的第一个划痕是这样的:

fun partition(orgl, encode) =
let
    val part = size(orgl)
    fun porpt(str, i, len) =
        if i = len - 1 then
            [substring(str, len * (len - 1), size(str) - (len - 1) * len)]
        else
            substring(str, len * i, len)::porpt(str, i + 1, len)
in
    porpt(encode, 0, part)
end;

但显然不能检查两个子串是否匹配相同的字符，除了按比例分割字符串还有很多其他的可能性。

这个问题的合适算法应该是什么？

附言只允许前缀代码。

---

我所学的知识还没有真正进入严肃的算法，但我做了一些关于回溯的搜索并编写了我的第二版代码:

fun partition(orgl, encode) =
let
    val part = size(orgl)
    fun backtrack(str, s, len, count, code) =
        let
           val current =
               if count = 1 then
                  code@[substring(str, s, size(str) - s)]
               else
                  code@[substring(str, s, len)]
        in
           if len > size(str) - s then []
           else
              if proper_prefix(0, orgl, code) then
                  if count = 1 then current
                  else
                     backtrack(str, s + len, len, count - 1, current)
              else
                 backtrack(str, s, len + 1, count, code)
        end
 in
    backtrack(encode, 0, 1, part, [])
 end;

函数 proper_prefix 将检查前缀代码和唯一映射。但是，此功能无法正常运行。

例如，当我输入:

partition("abcd", "001111110101101");

返回结果为:

uncaught exception Subscript

仅供引用，proper_prefix 的主体如下所示:

fun proper_prefix(i, orgl, nil) = true
  | proper_prefix(i, orgl, x::xs) =
    let
      fun check(j, str, nil) = true
        | check(j, str, x::xs) =
          if String.isPrefix str x then
             if str = x andalso substring(orgl, i, 1) = substring(orgl, i + j + 1, 1) then
                check(j + 1, str, xs)
             else
                false
          else
             check(j + 1, str, xs)
    in
      if check(0, x, xs) then proper_prefix(i + 1, orgl, xs)
      else false
    end;

Answer 1

我会尝试回溯方法:

从一个空假设开始(即将所有编码设置为未知)。然后逐个字符地处理编码后的字符串。

在每个新代码字符处，您有两个选择:将代码字符附加到当前源字符的编码或转到下一个源字符。如果您遇到您已有编码的源字符，请检查它是否匹配并继续。或者，如果不匹配，请返回并尝试其他选项。您还可以在此遍历期间检查前缀属性。

您的示例输入可以按如下方式处理:

Assume 'a' == '0'
Go to next source character
Assume 'b' == '0'
Violation of prefix property, go back
Assume 'a' == '00'
Go to next source character
Assume 'b' == '1'
...

这探索了所有可能编码的范围。您可以返回找到的第一个编码或所有可能的编码。