Ruby中字符串字典中的快速模糊/近似搜索

Question

我有一个50K到100K字符串的字典(最多可以有50多个字符),我试图找到一个给定的字符串是否在字典中具有一些"编辑"距离容差.(例如Levenshtein).在进行搜索之前,我很好地预先计​​算任何类型的数据结构.

我的目标是尽可能快地对该字典运行数千个字符串并返回最近的邻居.我会很好的只是得到一个布尔值,说明一个给定是否在字典中,如果有一个明显更快的算法这样做

为此,我首先尝试计算所有Levenshtein距离并采取最小值并且显然非常慢.所以我尝试在这篇文章的基础上实现Levenshtein Trie http://stevehanov.ca/blog/index.php?id=114

请参阅我的要点以重现基准:https://gist.github.com/nicolasmeunier/7493947

以下是我在机器上的一些基准测试:

编辑距离0(完美匹配)

Benchmark.measure { 10.times { dictionary.search(random_word, 0) } }
<Benchmark::Tms:0x007fa59bad8908 @label="", @real=0.010889, @cstime=0.0, @cutime=0.0, @stime=0.0, @utime=0.00999999999999801, @total=0.00999999999999801> 

*编辑距离2,变得慢很多*

Benchmark.measure { 10.times { dictionary.search(random_word, 2) } }
<Benchmark::Tms:0x007fa58c9ca778 @label="", @real=3.404604, @cstime=0.0, @cutime=0.0, @stime=0.020000000000000018, @utime=3.3900000000000006, @total=3.4100000000000006>

它从那里走下坡路,并且编辑距离大于2时变得非常慢.(每个测试字符串的平均值超过1秒).

我想知道如何/如果我可以显着加快这一点.如果现有的解决方案已经在ruby/gem中实现,我也不想重新发明轮子......

编辑1:在我的情况下,我希望我与字典匹配的大多数字符串不在那里.因此,如果有任何算法可以快速丢弃字符串,那可能会有所帮助.

谢谢,尼古拉斯

Answer 1

大约15年前,我写了模糊搜索,可以找到N关闭邻居.这是我对Wilbur的trigram算法的修改,这个修改名为"Wilbur-Khovayko算法".

基本思想:通过三元组分割字符串,并搜索最大交集分数.

例如,让我们有字符串"hello world".这个字符串生成三元组:hel ell llo"lo","o_w",eand等等; 此外,为每个单词生成特殊的前缀/后缀三元组,如$ he $ wo lo $ ld $.

此后,对于每个三元组构建的索引,在哪个术语中存在.

因此,这是每个trigram的term_ID列表.

当用户调用某个字符串时 - 它也会分割为三元组,并编程搜索最大交集分数,并生成N大小的列表.

它工作得很快:我记得,在老太阳/ solaris上,256MB RAM,200MHZ CPU,它在字典5,000,000条中搜索100个最近的术语,在0.25秒内

你可以从http://olegh.ftp.sh/wilbur-khovayko.tar.gz获取我的旧资料

更新:

我创建了新的存档,其中Makefile已针对现代Linux/BSD make进行了调整.你可以在这里下载新版本:http://olegh.ftp.sh/wilbur-khovayko.tgz

制作一些目录,并在此处提取存档:

mkdir F2
cd F2
tar xvfz wilbur-khovayko.tgz
make

转到测试目录,复制术语列表文件(这是固定名称,termlist.txt),并制作索引:

 cd test/
 cp /tmp/test/termlist.txt ./termlist.txt
 ./crefdb.exe <termlist.txt

在这个测试中,我使用了〜380,000个过期的域名:

wc -l termlist.txt
379430 termlist.txt

运行findtest应用程序:

./findtest.exe

boking  <-- this is query -- word "booking" with misspeling


0001:Query: [boking]
  1:  287890 (  3.863739) [bokintheusa.com,2009-11-20,$69]
  2:  287906 (  3.569148) [bookingseu.com,2009-11-20,$69]
  3:  257170 (  3.565942) [bokitko.com,2009-11-18,$69]
  4:  302830 (  3.413791) [bookingcenters.com,2009-11-21,$69]
  5:  274658 (  3.408325) [bookingsadept.com,2009-11-19,$69]
  6:  100438 (  3.379371) [bookingresorts.com,2009-11-09,$69]
  7:  203401 (  3.363858) [bookinginternet.com,2009-11-15,$69]
  8:  221222 (  3.361689) [bobokiosk.com,2009-11-16,$69]
  . . . . 
 97:   29035 (  2.169753) [buccupbooking.com,2009-11-05,$69]
 98:  185692 (  2.169047) [box-hosting.net,2009-11-14,$69]
 99:  345394 (  2.168371) [birminghamcookinglessons.com,2009-11-25,$69]
100:  150134 (  2.167372) [bowlingbrain.com,2009-11-12,$69]

Answer 2

我写了一对宝石,模糊和模糊,它们做基于三卦的模糊匹配.鉴于您的(低)数据量,Fuzzily将更容易集成,并且速度快,您可以在现代硬件上获得5-10ms内的答案.

鉴于两者都是基于三元组(可索引),而不是基于编辑距离(不是),您可能必须在两个过程中执行此操作:

• 首先要求宝石获得一组最佳匹配三卦
• 然后使用Levenstein将结果与输入字符串进行比较
• 并返回该度量的最小值.

在Ruby中(如您所知),使用Fuzzily + Text gem,获取具有编辑距离阈值的记录将如下所示:

MyRecords.find_by_fuzzy_name(input_string).select { |result|
  Text::Levenshtein.distance(input_string, result.name)] < my_distance_threshold
}

这执行了一些优化良好的数据库查询和一些

注意事项:

• 如果你所寻找的"最小"编辑距离很高,你仍然会做很多Levenshteins.
• 使用trigrams假设您的输入文本是拉丁文本或接近(基本上是欧洲语言).
• 可能存在边缘情况,因为没有任何保证"匹配三卦的数量"是"编辑距离"的一般近似值.