如何在另一个字符串中找到可能出现的子字符串？

Question

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

• 宪法
• 阿布拉达布拉
• 电冰箱
• 堆栈过流

我有一个“损坏”的句子，在那里可以找到那些字符串的重要子字符串，没有特定的顺序或特定的计数。这些词也不一定是明确分开的。

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

下面是一个示例输入：

[医][医]

根据这一输入，我希望能够重建这一系列已知的单词：

'abracadabra'，‘体质’，‘abracadabra’，‘冰箱’，'abracadabrea'，'stackoverflow'，‘冰箱’

句子很短(通常是5-6个单词)，所以我可以负担得起需要记忆和能量的算法。而且，损坏总是仅限于每个单词的几个首字母和最后一个字符；中间的字符总是正确的(这就是为什么我要寻找大的子字符串)。

有什么想法吗？由于单词没有清楚地分开，所以普通编辑距离并不能做到这一点。

Answer 1

因为你的字典里的单词很少，而且单词本身也很小，所以我只想在字典中查找每个单词的所有可能的子串。当然，查找大小为0或1的子字符串是毫无意义的，您可能希望对单词的大小有一个较低的阈值。

对于每个子字符串，您可以简单地在句子中查找它，如果它发生了，您可以将它标记为可能是句子的一部分。为了加快速度，您可能需要在O(n)中的句子中进行搜索(例如使用KMP或拉宾·卡普)。

下面是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"))

Answer 2

根据您所说的问题的大小，我根本不会担心优化这个解决方案，因为任何低于指数的东西都会立即运行。我只会给你一个算法，我很肯定能给出一个正确的答案，就像你所期望的那样，对于这样一个半模糊的问题。然后我们就可以优化它了。

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

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

如果您担心速度，您可以设置一个最大字长，生成ws的成本会下降到字符串长度的线性。

把你的一组单词依次倒入f中，你可以使用任何你想要的启发式方法来确定哪些词是从你的字典中选择出来的，或者当你选择的单词重叠时该怎么做。一个简单的实现可以根据开始字母索引对所有单词进行排序，而f在任何时候返回一个匹配项，跳过字母直到所选单词结束。

Answer 3

您可以尝试使用Levenshtein距离算法来查找与字典中的单词距离最小的单词(定义容忍)。

祝好运!