用于查找字符串中最常见子字符串的算法

Question

是否有任何算法可用于查找字符串中最常见的短语(或子串)？例如,以下字符串将"hello world"作为其最常见的双字短语:

"hello world this is hello world. hello world repeats three times in this string!"

在上面的字符串中,最常见的字符串(在空字符串字符之后,重复无限次数)将是空格字符.

有没有办法在这个字符串中生成一个公共子串列表,从最常见到最不常见？

Answer 1

这是类似于Nussinov算法的任务,实际上甚至更简单,因为我们不允许对齐中的任何间隙,插入或不匹配.

对于长度为N的字符串A,定义一个F[-1 .. N, -1 .. N]表并使用以下规则填写:

  for i = 0 to N
    for j = 0 to N
      if i != j
        {
          if A[i] == A[j]
            F[i,j] = F [i-1,j-1] + 1;
          else
            F[i,j] = 0;
        }

例如,对于BA O BA B:

这会O(n^2)及时运行.表中的最大值现在指向最长自匹配子序列的结束位置(i - 一个出现的结束,j - 另一个).在开始时,假设该数组是零初始化的.我添加了条件来排除最长但可能不是有趣的自我匹配的对角线.

更重要的是,这个表在对角线上是对称的,所以它只能计算一半.此外,该阵列初始化为零,因此分配零是多余的.那仍然存在

  for i = 0 to N
    for j = i + 1 to N
      if A[i] == A[j]
         F[i,j] = F [i-1,j-1] + 1;

更短但可能更难理解.计算表包含所有匹配,short和long.您可以根据需要添加进一步的过滤.

在下一步,您需要恢复字符串,从非零单元格向上和向左对角线.在此步骤中,使用一些散列映射来计算同一字符串的自相似性匹配的数量也很简单.使用正常字符串和正常最小长度,将只通过此映射处理少量表格单元格.

我认为直接使用hashmap实际上需要O(n ^ 3),因为必须以某种方式比较访问结束时的关键字符串是否相等.这种比较可能是O(n).

Answer 2

蟒蛇.这有点快速和肮脏,数据结构完成了大部分工作.

from collections import Counter
accumulator = Counter()
text = 'hello world this is hello world.'
for length in range(1,len(text)+1):
    for start in range(len(text) - length):
        accumulator[text[start:start+length]] += 1

Counter结构是一个哈希支持的字典,用于计算你看到过多少次.添加到不存在的密钥将创建它,而检索不存在的密钥将给出零而不是错误.所以你要做的就是迭代所有的子串.