来自 NLP 输入的字符串匹配

Question

我在和 Alexa 开玩笑。我的任务是将用户输入与从网络动态加载的可能答案列表相匹配。在本例中，它是电影列表。

当然，我不能假设总会有完美匹配，用户或 Echo 设备都不会完全正确。我目前克服这个问题的方法是 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"，则会发生这种情况：

# 0.62069 Die Verurteilten
# 0.55319 Der Herr der Ringe - Die Gefährten
# Die Verurteilten

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

谢谢。

Answer 1

该对象的文档在方法方面不是很详细，但我的猜测是使用了 Levenshtein 距离方法。

这有可能在您的用例中失败，因为额外的 'Der Herr Der Ringe' 破坏了此方法的 'score'，因为 'Die Verurteilten' 需要更少的加法，减法 and/or 替换以匹配您的查询。

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

您可以使用令牌匹配方法，其中您的 'score' 主要依赖于单个匹配词。因此，'Die Gefährten's 在 'Der Herr der Ringe - Die Gefährte' 中匹配它的两个词，将其标记为 100% 匹配。这可以与其他字符级方法（如 levenshtein 和 ngram 字符）结合使用，以在识别特定标记匹配和潜在的、接近的标记匹配方面产生平衡的结果。

或者您可以将 haystack aka 语料库分块成 'chunks' n 长的标记以进行比较。您需要能够比较这些结果的分数，因为即使是一个列表，您也可能有多个匹配项，但是，您应该能够识别 [=26= 中的 'Die Gefährte' 的完全匹配项] 作为 100% 匹配。

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

Answer 2

根据 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)

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

# 0.55319 Der Herr der Ringe - Die Gefährten
# 0.32653 Die zwölf Geschworenen
# 0.29557 Die Verurteilten

广泛的测试将证明这个解决方案到底有多有效。

来自 NLP 输入的字符串匹配

String matching from NLP input

python

nlp

string-matching

alexa