5

字符串“abab”可以被认为是索引符号“0101”的模式。字符串“bcbc”也将由“0101”表示。这非常漂亮，并且可以进行强大的比较，但它很快就会从完美的案例中分崩离析。

“babcbc”将是“010202”。如果我想指出它包含等于“0101”（bcbc 部分）的模式，我只能考虑在每个索引处进行某种标准化过程，以象征性地“重新表示”从 n 到 length 的子字符串以进行比较. 如果我想看看“babcbc”和“dababd”（010202 与 012120）是否有任何共同点，那就变得复杂了。这么低效！

如何有效地做到这一点，照顾所有可能的嵌套案例？请注意，我正在寻找类似的模式，而不是实际文本中的类似子字符串。

4

3 回答 3

1

尝试将每个字符替换为 min(K, 与该字符之前出现的距离)，其中 K 是一个可调常数，因此 babcbc 和 dababd 变为类似于 KK2K22 和 KKK225。您可以使用后缀树或后缀数组在转换后的文本中查找重复。

于 2012-09-11T18:06:46.183 回答
0

您的算法因压缩字符串的原始数据集而丢失了信息，因此我不确定您是否可以在不做比比较原始字符串更多的工作的情况下恢复完整的信息集。此外，虽然您的数据集看起来更易于人类阅读，但它当前占用的空间与原始字符串一样多，并且字符串的差异图（其中值是前一个字符和当前字符之间的距离）可能具有更具可比性的信息放。

但是，关于如何检测所有公共子集，您应该查看 Least Common Subsequence 算法以找到最大的匹配模式。这是一个定义明确的算法并且效率很高——O(n * m)，其中 n 和 m 是字符串的长度。请参阅SO和Wikipedia上的 LCS 。如果您还想查看环绕字符串的模式（作为循环搅拌 - 在哪里abeab和eabab应该匹配），那么您需要一个环形 LCS，它在Andy Nguyen的论文中有所描述。

您需要稍微更改算法以考虑到目前为止的变化数量。我的建议是在 LCS 表中添加两个额外的维度，表示在两个原始字符串的过去 k 个字符中遇到的唯一数字的数量以及每个字符串的压缩版本。然后你可以做一个 LCS 解决方案，你总是朝着与压缩字符串匹配的方向移动，并且为过去的 k 个字符匹配两个字符串中相同数量的唯一字符。这应该对所有可能的唯一子字符串匹配进行编码。

棘手的部分将始终选择最大化包含相同数量唯一字符的 k 的方向。因此，在 LCS 表的每个元素中，您将有一个额外的字符串搜索来搜索 k 值的最佳步骤。由于更长的序列总是包含所有可能的更小的序列，如果你最大化你在每一步中的 k 个选择，你知道下一次迭代中的最佳 k 最多是 1 步，所以一旦 4D 表被填写，它应该是可以以与原始 LCS 表类似的方式求解。请注意，因为您有一个 4D 表格，所以逻辑确实变得更加复杂，但是如果您阅读 LCS 的工作原理，您将能够看到如何定义一致的规则，以便在每个步骤中向左上角移动。因此 LCS 算法保持不变，只是扩展到更多维度。

这个解决方案一旦完成就会非常复杂，所以你可能想重新考虑你想要实现的目标/如果这个模式在你开始编写这样的算法之前编码了你真正想要的信息。

于 2012-09-11T17:53:07.390 回答
0

这是一个使用 Prolog 的统一功能和属性变量来匹配模板的解决方案：

:-dynamic pattern_i/3.

test:-
  retractall(pattern_i(_,_,_)),
  add_pattern(abab),
  add_pattern(bcbc),
  add_pattern(babcbc),
  add_pattern(dababd),
  show_similarities.

show_similarities:-
  call(pattern_i(Word, Pattern, Maps)),
  match_pattern(Word, Pattern, Maps),
  fail.
show_similarities.

match_pattern(Word, Pattern, Maps):-
  all_dif(Maps), % all variables should be unique
  call(pattern_i(MWord, MPattern, MMaps)),
  Word\=MWord,
  all_dif(MMaps),
  append([_, Pattern, _], MPattern), % Matches patterns
  writeln(words(Word, MWord)),
  write('mapping: '),
  match_pattern1(Maps, MMaps). % Prints mappings

match_pattern1([], _):-
  nl,nl.
match_pattern1([Char-Char|Maps], MMaps):-
  select(MChar-Char, MMaps, NMMaps),
  write(Char), write('='), write(MChar), write(' '),
  !,
  match_pattern1(Maps, NMMaps).

add_pattern(Word):-
  word_to_pattern(Word, Pattern, Maps),
  assertz(pattern_i(Word, Pattern, Maps)).

word_to_pattern(Word, Pattern, Maps):-
  atom_chars(Word, Chars),
  chars_to_pattern(Chars, [], Pattern, Maps).

chars_to_pattern([], Maps, [], RMaps):-
  reverse(Maps, RMaps).
chars_to_pattern([Char|Tail], Maps, [PChar|Pattern], NMaps):-
  member(Char-PChar, Maps),
  !,
  chars_to_pattern(Tail, Maps, Pattern, NMaps).
chars_to_pattern([Char|Tail], Maps, [PChar|Pattern], NMaps):-
  chars_to_pattern(Tail, [Char-PChar|Maps], Pattern, NMaps).

all_dif([]).
all_dif([_-Var|Maps]):-
  all_dif(Var, Maps),
  all_dif(Maps).

all_dif(_, []).
all_dif(Var, [_-MVar|Maps]):-
  dif(Var, MVar),
  all_dif(Var, Maps).

该算法的思想是：

  • 为每个单词生成一个未绑定变量的列表，我们对单词中的相同字符使用相同的变量。例如：对于单词 abcbc，列表看起来像 [X,Y,Z,Y,Z]。这定义了这个词的模板
  • 一旦我们有了模板列表，我们就可以获取每个模板并尝试将模板与每个其他单词的子模板统一起来。例如，如果我们有单词 abcbc 和 zxzx，则模板将是 [X,Y,Z,Y,Z] 和 [H,G,H,G]。然后在第一个模板上有一个子模板，它与第二个单词的模板统一（H=Y，G=Z）
  • 对于每个模板匹配，我们显示产生该匹配所需的替换（变量重命名）。所以在我们的例子中，替换是 z=b, x=c

测试输出（单词 abab、bcbc、babcbc、dababd）：

?- test.

words(abab,bcbc)
mapping: a=b b=c 

words(abab,babcbc)
mapping: a=b b=c 

words(abab,dababd)
mapping: a=a b=b 

words(bcbc,abab)
mapping: b=a c=b 

words(bcbc,babcbc)
mapping: b=b c=c 

words(bcbc,dababd)
mapping: b=a c=b
于 2012-09-11T19:02:05.163 回答