26

是否有任何算法可用于查找字符串中最常见的短语（或子字符串）？例如，以下字符串将“hello world”作为其最常见的两个词短语：

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

在上面的字符串中，最常见的字符串（在空字符串字符之后，重复无数次）是空格字符。

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

4

5 回答 5

15

这与 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;

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

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

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

于 2013-02-03T08:24:56.457 回答
6

Python。这有点快速和肮脏，数据结构完成了大部分工作。

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 结构是一个哈希支持的字典，旨在计算您看到某物的次数。添加到不存在的密钥将创建它，而检索不存在的密钥将为您提供零而不是错误。因此，您所要做的就是遍历所有子字符串。

于 2013-02-03T08:35:55.597 回答
2

只是伪代码，也许这不是最漂亮的解决方案，但我会这样解决：

function separateWords(String incomingString) returns StringArray{
  //Code
}

function findMax(Map map) returns String{
  //Code
}

function mainAlgorithm(String incomingString) returns String{
    StringArray sArr = separateWords(incomingString);
    Map<String, Integer> map; //init with no content
    for(word: sArr){
        Integer count = map.get(word);
        if(count == null){
            map.put(word,1);
        } else {
            //remove if neccessary
            map.put(word,count++); 
        }
   }
   return findMax(map);
}

其中 map 可以包含一个键值对，如 Java HashMap 中的。

于 2013-02-04T15:44:31.523 回答
0

Perl，O(n²)解决方案

my $str = "hello world this is hello world. hello world repeats three times in this string!";

my @words = split(/[^a-z]+/i, $str);
my ($display,$ix,$i,%ocur) = 10;

# calculate

for ($ix=0 ; $ix<=$#words ; $ix++) {
  for ($i=$ix ; $i<=$#words ; $i++) {
    $ocur{ join(':', @words[$ix .. $i]) }++;
  }
}

# display 

foreach (sort { my $c = $ocur{$b} <=> $ocur{$a} ; return $c ? $c : split(/:/,$b)-split(/:/,$a); } keys %ocur) {
  print "$_: $ocur{$_}\n";
  last if !--$display;
}

显示最常见子字符串的 10 个最佳分数（如果出现平局，首先显示最长的单词链）。改为只有结果$display。有迭代。1
n(n+1)/2

于 2013-02-03T12:53:23.377 回答
0

由于对于长度 >= 2 的字符串的每个子字符串，文本至少包含一个长度为 2 的子字符串，因此我们只需要研究长度为 2 的子字符串。

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

val li = s.sliding (2, 1).toList
// li: List[String] = List(he, el, ll, lo, "o ", " w", wo, or, rl, ld, "d ", " t", th, hi, is, "s ", " i", is, "s ", " h", he, el, ll, lo, "o ", " w", wo, or, rl, ld, d., ". ", " h", he, el, ll, lo, "o ", " w", wo, or, rl, ld, "d ", " r", re, ep, pe, ea, at, ts, "s ", " t", th, hr, re, ee, "e ", " t", ti, im, me, es, "s ", " i", in, "n ", " t", th, hi, is, "s ", " s", st, tr, ri, in, ng, g!)

val uniques = li.toSet
uniques.toList.map (u => li.count (_ == u))
// res18: List[Int] = List(1, 2, 1, 1, 3, 1, 5, 1, 1, 3, 1, 1, 3, 2, 1, 3, 1, 3, 2, 3, 1, 1, 1, 1, 1, 3, 1, 3, 3, 1, 3, 1, 1, 1, 3, 3, 2, 4, 1, 2, 2, 1)

uniques.toList(6)
res19: String = "s "
于 2018-03-06T10:19:54.267 回答