NLP inpu的字符串匹配

Question

我在和亚历克斯鬼混。我的任务是将用户输入与从web动态加载的可能答案列表相匹配。在这个例子中，它是一个电影列表。在

当然，我不能假设总会有一个完美的匹配，无论是用户还是回声设备都不能很好地匹配。我目前克服这个问题的方法是SequenceMatcher函数。因此，我测量用户输入和列表中所有项目的相似性，最终胜出者可能是用户真正谈论的列表项：

from difflib import SequenceMatcher

maxi = 0
haystack = ["Die Verurteilten", "Der Pate", "Der Pate 2", "The Dark Knight", "Die zwölf Geschworenen", "Schindlers Liste", "Pulp Fiction", "Der Herr der Ringe - Die Rückkehr des Königs", "Zwei glorreiche Halunken", "Fight Club", "Der Herr der Ringe - Die Gefährten", "Forrest Gump", "Das Imperium schlägt zurück", "Inception", "Der Herr der Ringe - Die zwei Türme", "einer flog über das Kuckucksnest", "GoodFellas - Drei Jahrzehnte in der Mafia", "Matrix", "Die sieben Samurai", "Krieg der Sterne", "City of God", "Sieben", "Das Schweigen der Lämmer", "Ist das Leben nicht schön?", "Das Leben ist schön"]
needle = "Die Gefährten"

for hay in haystack:
    ratio = SequenceMatcher(None, needle, hay).ratio()
    print('%.5f' % ratio + " " + hay)
    if ratio > maxi:
        maxi = ratio
        result = hay

print(result)

大多数时候我对结果很满意。然而，有时候（也有点太频繁了）我不是。如果用户可能会像上面的例子那样要求“Die Gefährten”，则会发生这种情况：

^{pr2}$

对于这种特殊情况，用分隔符-分割列表项，对所有结果部分进行计算并返回最大分数，这可能是一个简单的解决方案。但由于清单上可能有其他东西（食谱、书籍、歌曲、游戏等等），我想知道是否有更普遍的方法。有什么想法吗？在

谢谢。在

Answer 1

根据John的输入，我创建了以下例程。在

除了前面的计算，我还做了一个单独的单词匹配，并计算出所有单词的平均分数由Alexa提供。在

总分是两个分数的乘积。在

我还试图忽略任何基于字长的假设填充词。基于一个非常基本的统计摘要（字数和中间字长），我将忽略所有字长小于5、4或2个字元的字词。使用字典可能是一个更好的解决方案，但由于多语言环境，我想避免这种情况。在

from difflib import SequenceMatcher
from statistics import median, mean

def getWords(input):
    words = input.split()
    lengths = [ len(x) for x in words if len(x) > 1 ]

    # set the minimum word length based on word count
    # and median of word length to remove presumed fillers
    minLength = 2
    if len(words) >= 3 and median(lengths) > 4:
        minLength = 5
    elif len(words) >= 2 and median(lengths) > 3:
        minLength = 4

    # keep words of minimum length
    answer = list()
    for item in words:
        if len(item) >= minLength:
            answer.append(item) 

    return answer

matchList = ["Die Verurteilten", "Der Pate", "Der Pate 2", "The Dark Knight", "Die zwölf Geschworenen", "Schindlers Liste", "Pulp Fiction", "Der Herr der Ringe - Die Rückkehr des Königs", "Zwei glorreiche Halunken", "Fight Club", "Der Herr der Ringe - Die Gefährten", "Forrest Gump", "Das Imperium schlägt zurück", "Inception", "Der Herr der Ringe - Die zwei Türme", "Einer flog über das Kuckucksnest", "GoodFellas - Drei Jahrzehnte in der Mafia", "Matrix", "Die sieben Samurai", "Krieg der Sterne", "City of God", "Sieben", "Das Schweigen der Lämmer", "Ist das Leben nicht schön?", "Das Leben ist schön"]
userInput = "Die Gefährten"

# find the best match between the user input and the link list
maxi = 0
for matchItem in matchList:

    # ratio of the original item comparison
    fullRatio = SequenceMatcher(None, userInput, matchItem).ratio()

    # every word of the user input will be compared
    # to each word of the list item, the maximum score
    # for each user word will be kept
    wordResults = list()
    for userWord in getWords(userInput):
        maxWordRatio = 0
        for matchWord in getWords(matchItem):
            wordRatio = SequenceMatcher(None, userWord, matchWord).ratio()
            if wordRatio > maxWordRatio:
                maxWordRatio = wordRatio 
        wordResults.append(maxWordRatio)

    # the total score for each list item is the full ratio
    # multiplied by the mean of all single word scores
    itemScore = fullRatio * mean(wordResults)

    # print item result
    print('%.5f' % itemScore, matchItem)

    # keep track of maximum score
    if itemScore > maxi:
        maxi = itemScore
        result = matchItem

# award ceremony
print(result)

此例程的排名输出（更好）：

^{pr2}$

广泛的测试将告诉我们这个解决方案到底有多有效。在

Answer 2

关于这个对象的文档在方法论方面还不是很详细，但是我想使用的是Levenshtein距离方法。在

这有可能在您的用例中失败，因为额外的“derherr Der Ringe”会破坏此方法的“score”，因为“Die Verurteilten”需要较少的加法、减法和/或替换来匹配您的查询。在

您的问题有两种解决方案：

你可以使用标记匹配方法，在这种方法中，你的“分数”很大程度上取决于单个匹配词。所以“Die Gefährten’s matching the two words in‘Der Herr Der Ringe-Die Gefährte’标记为100%匹配。这可以与其他字符级方法（如levenshtein和ngram character）相结合，产生一个平衡的结果，既能识别特定的令牌匹配，又能识别潜在的、接近的令牌匹配。在

或者你可以把你的干草堆aka语料库分成'chunks'n个长的标记进行比较。你需要能够比较这些结果的分数，因为你可能在一个列表上有不止一个匹配，但是你应该能够识别出与“Der Herr Der Ringe-Die Gefährte”中的“Die Gefährte”完全匹配。在

实际上，您需要将您的问题从模糊匹配问题重新定义为从非结构化文本中识别命名实体的问题，也许使用一点模糊匹配来补偿Alexa产生的任何garbledygook。在