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

我有一个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) } }

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

 Benchmark.measure { 10.times { dictionary.search(random_word, 2) } }

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

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

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

谢谢，尼古拉斯

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

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

  • 首先要求gem获得一组最佳匹配三卦
  • 然后使用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假设您的输入文本是拉丁文本或接近（基本上是欧洲语言）。
  • 可能存在边缘情况，因为没有任何保证“匹配三卦的数量”是对“编辑距离”的一般近似。

大约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

在这个测试中，我使用了〜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]

如果您准备参与机器学习方法，那么Geoff Hinton的这篇论文将是一个很好的起点

http://www.cs.toronto.edu/~hinton/absps/sh.pdf

这些方法在Google等地方使用。

基本上，您根据相似性对字典字符串进行聚类。 当查询字符串到来时，您只需比较集群，而不是计算整个数据集的编辑距离，从而显着缩短查询时间。

PS我做了一些谷歌搜索，发现另一个类似的方法的Ruby实现称为Locality Sensitive Hashing https://github.com/bbcrd/ruby-lsh

这是原始的类似Trie的实现。 它完全没有优化，只是一个概念certificate。 纯Ruby实现。

为了测试它，我从这里获取了100_000个单词http://www.infochimps.com/datasets/word-list-100000-official-crossword-words-excel-readable/downloads/195488

这是它的要点https://gist.github.com/fl00r/7542994 

 class TrieDict attr_reader :dict def initialize @dict = {} end def put(str) d = nil str.chars.each do |c| d && (d = (d[1][c] ||= [nil, {}])) || d = (@dict[c] ||= [nil, {}]) end d[0] = true end def fetch(prefix, fuzzy = 0) storage = [] str = "" error = 0 recur_fetch(prefix, fuzzy, @dict, storage, str, error) storage end def recur_fetch(prefix, fuzzy, dict, storage, str, error) dict.each do |k, vals| e = error if prefix[0] != k e += 1 next if e > fuzzy end s = str + k storage << s if vals[0] && (prefix.size - 1) <= (fuzzy - e) recur_fetch(prefix[1..-1] || "", fuzzy, vals[1], storage, s, e) end end end def bench t = Time.now.to_f res = nil 10.times{ res = yield } e = Time.now.to_f - t puts "Elapsed for 10 times: #{e}" puts "Result: #{res}" end trie = TrieDict.new File.read("/home/petr/code/tmp/words.txt").each_line do |word| trie.put(word.strip) end; :ok # Elapsed for 10 times: 0.0006465911865234375 # Result: ["hello"] bench{ trie.fetch "hello", 1 } # Elapsed for 10 times: 0.013643741607666016 # Result: ["cello", "hallo", "helio", "hell", "hello", "hellos", "hells", "hillo", "hollo", "hullo"] bench{ trie.fetch "hello", 2 } # Elapsed for 10 times: 0.08267641067504883 # Result: ["bell", "belle", "bellow", "bells", "belly", "cell", "cella", "celli", "cello", "cellos", "cells", "dell", "dells", "delly", "fell", "fella", "felloe", "fellow", "fells", "felly", "hall", "hallo", "halloa", "halloo", "hallos", "hallot", "hallow", "halls", "heal", "heals", "heel", "heels", "heil", "heils", "held", "helio", "helios", "helix", "hell", "helled", "heller", "hello", "helloed", "helloes", "hellos", "hells", "helm", "helms", "helot", "help", "helps", "helve", "herl", "herls", "hill", "hillo", "hilloa", "hillos", "hills", "hilly", "holla", "hollo", "holloa", "holloo", "hollos", "hollow", "holly", "hull", "hullo", "hulloa", "hullos", "hulls", "jell", "jells", "jelly", "mell", "mellow", "mells", "sell", "selle", "sells", "tell", "tells", "telly", "well", "wells", "yell", "yellow", "yells"] bench{ trie.fetch "engineer", 2 } # Elapsed for 10 times: 0.04654884338378906 # Result: ["engender", "engine", "engined", "engineer", "engineered", "engineers", "enginery", "engines"] bench{ trie.fetch "engeneer", 1 } # Elapsed for 10 times: 0.005484580993652344 # Result: ["engender", "engineer"]
Interesting Posts