如何在一个字符串中找到子字符串的可能出现位置？涉及到IT技术。

Question

假设我有一个字符串集合：

• constitution
• abracadabra
• refrigerator
• stackoverflow

现在我有一个"损坏"的句子，其中可以找到集合中字符串的重要子串，但没有特定顺序或具体数量。这些单词的分隔也不一定明显。

有什么算法能帮我在损坏的句子中找到集合中最可能出现的字符串？

这是一个示例输入：

xbracadabrqbonstitution ibracadabrefrigeratos obracadabri xtackoverflotefrigeratos

从这个输入中，我期望能够重构出以下已知单词的数组：

['abcracadabra', 'constitution', 'abracadabra', 'refrigerator', 'abracadabrea', 'stackoverflow', 'refrigerator']

句子非常短（通常只有5-6个单词），因此可以使用占用内存和计算资源较多的算法。而且，损坏总是局限于每个单词的前几个和后几个字符；中间总是正确的（这就是为什么我要寻找大的子串的原因）。

有什么想法吗？由于单词不是明显分开的，因此普通的编辑距离不能解决问题。

- zneak

---

你的字典里会有多少个单词？每个单词可以有多大？ - MAK

@MAK，我的字典很小（15-20个单词），而且这些单词本身也很短（5-7个字符长）。我使用更长的单词来说明我的问题，并使中间部分保持不变。还原后，句子的长度可以在5到20个单词之间变化。 - zneak

Answer 1

基于你表述的问题规模，我不会担心优化这个解决方案，因为只要不是指数级别的，运行速度都很快。我只会给你一个算法，我非常确定它可以给出类似这种模糊问题的正确答案。然后我们可以着手优化它。

首先，你需要任何启发式函数 f，它接受一个单词 w 并返回最接近的单词或无匹配项。

然后你只需生成字符串中所有可能的 w 的集合。在最坏的情况下，这意味着获取所有长度为 1、2、3 直到字符串长度的所有字符串的集合。用这种方式生成的 w 的总数将约为 (n * n-1) / 2

如果你担心速度问题，可以设置最大单词长度，这样生成 ws 的成本就会退回到与你字符串长度线性相同的水平。

将你的单词集合一个接一个地放入f中，你可以使用任何启发式方法来确定从你的字典中选择哪些单词作为真正的单词，或者当你选择的单词重叠时该怎么办。一个简单的实现可能会按起始字母索引对所有单词进行排序，每当f返回匹配项时，跳过字母直到所选单词的末尾。

- dhakim

Answer 2

由于您的字典中单词很少，而且单词本身很小，我建议尝试查找字典中每个单词的所有可能子字符串。当然，查找大小为0或1的子字符串是没有意义的，您可能希望对单词的大小设置较低的阈值。

对于每个子字符串，您可以在句子中简单地查找它，如果出现，则可以将其标记为可能是句子的一部分。为了提高速度，您可能希望在句子内进行O(n)的搜索（例如使用KMP或Rabin Karp）

以下是Python中该想法的简单实现（使用暴力字符串匹配）：

d=["constitution","abracadabra","refrigerator","stackoverflow"]

def substring_match(word,sentence,min_length):
    for start in xrange(0,len(word)):
        for end in xrange(start+min_length,len(word)):
            substr=word[start:end+1]
            if substr in sentence:
                return True
    return False

def look_for_words(word_dict,sent_word):
    return [word for word in word_dict if substring_match(word,sent_word,5)]

def look(word_dict,sentence):
    ret=[]
    for word in sentence.split():
        ret.extend(look_for_words(word_dict,word))
    return ret

if __name__=='__main__':
    print "\n".join(look(d,"xbracadabrqbonstitution ibracadabrefrigeratos obracadabri xtackoverflotefrigeratos"))

- MAK

Answer 3

你可以尝试使用Levenshtein距离算法来查找与你的字典中的单词具有最小距离的单词（你可以定义容差）。

祝你好运！

- aviad

---

编辑距离在合并的单词上出现了问题。 :/ - zneak

我可以找到任何算法卡在合并单词上的边缘情况。如何处理这些情况取决于您。问题是您期望有多少个合并单词？无论如何，我发现了这个库http://alias-i.com/lingpipe/docs/api/com/aliasi/spell/JaccardDistance.html，它考虑了重叠并根据标记重叠计算距离。希望能有所帮助... - aviad

我的大部分单词都被合并了；在我的情况下，这不是一个边缘案例，因此我正在寻找一种可以处理这种情况的算法。我之所以提出这个问题，是因为我知道的用于处理字符串差异的算法在这种情况下失败了。Jaccard距离看起来很有前途，但我读了维基百科的描述，我不确定它是否真正能够处理这种情况。 - zneak

好吧，似乎没有现成的解决方案可以解决你的问题（至少我不知道有...）那么我们考虑使用距离来查找字典中最接近的候选项，然后逐一检查它们（蛮力法）。 - aviad