Levenshtein和Trigram的替代品

Question

假设我的数据库中有以下两个字符串:

(1) 'Levi Watkins Learning Center - Alabama State University'
(2) 'ETH Library'

我的软件从数据源接收自由文本输入,它应该将这些自由文本与数据库中的预定义字符串(上面的那些)相匹配.

例如,如果软件获得字符串'Alabama University',它应该认识到这与(1)它更相似(2).

起初,我想过使用像Levenshtein-Damerau或Trigrams这样众所周知的字符串度量,但这会导致不必要的结果,如下所示:

http://fuzzy-string.com/Compare/Transform.aspx?r=Levi+Watkins+Learning+Center+-+Alabama+State+University&q=Alabama+University

http://fuzzy-string.com/Compare/Transform.aspx?r=ETH+Library&q=Alabama+University

Difference to (1): 37
Difference to (2): 14

(2)获胜因为它比它短得多(1),即使(1)包含搜索字符串的单词(Alabama和University).

我也尝试过Trigrams(使用Javascript库fuzzySet),但我在那里得到了类似的结果.

是否有一个字符串指标可以识别搜索字符串的相似性(1)？

Answer 1

您可以尝试使用 Word Mover 的距离https://github.com/mkusner/wmd。该算法的一个显着优点是它在计算文档中单词之间的差异时结合了隐含含义。该论文可以在这里找到

Answer 2

关键词计数

您还没有真正定义为什么您认为选项一是“更接近”的匹配，至少在任何算法意义上都没有。看来您的期望基于选项一比选项二具有更多匹配关键字的概念，那么为什么不只根据每个字符串中的关键字数量进行匹配呢？

例如，使用 Ruby 2.0：

string1 = 'Levi Watkins Learning Center - Alabama State University'
string2 = 'ETH Library'
strings = [str1, str2]

keywords  = 'Alabama University'.split
keycount  = {}

# Count matching keywords in each string.
strings.each do |str|
  keyword_hits  = Hash.new(0)
  keywords.each { |word| keyword_hits[word] += str.scan(/#{word}/).count }
  keyword_count = keyword_hits.values.reduce :+
  keycount[str] =  keyword_count
end

# Sort by keyword count, and print results.
keycount.sort.reverse.map { |e| pp "#{e.last}: #{e.first}" }

这将打印：

“2：Levi Watkins 学习中心 - 阿拉巴马州立大学”
“0：ETH 图书馆”

这符合您对语料库的期望。您可能希望使用其他算法对结果进行额外的传递以优化结果或打破平局，但这至少应该让您指向正确的方向。