Sup*_*ing 57 algorithm data-structures
所以我需要编写一个有效的算法来查找字典中缺少字母的单词,我想要一组可能的单词.
例如,如果我有这个,我可能会回复这些,那些,主题,那些.
我想知道是否有人可以建议我应该使用的一些数据结构或算法.
谢谢!
编辑:特里太空间效率太低,太慢了.还有其他想法修改吗？
更新:最多会出现两个问号,当出现两个问号时,它们将按顺序出现.
目前我正在使用3个哈希表,当它是完全匹配,1个问号和2个问号时.给定一个字典我会散列所有可能的单词.例如,如果我有单词WORD.我哈希WORD,？ORD,W？RD,WO？D,WOR ?, ?? RD,W ?? D,WO ??.进入字典.然后我使用链接列表将冲突链接在一起.所以说hash(W？RD)= hash(STR？NG)= 17. hashtab(17)将指向WORD,WORD指向STRING,因为它是一个链表.
平均查找一个单词的时间约为2e-6s.我希望做得更好,最好是1e-9的顺序.
编辑:我没有再看过这个问题,但是3m条目插入需要0.5秒,3m条目查找需要4秒.
谢谢!
mar*_*nus 66
我相信在这种情况下,最好只使用一个平面文件,其中每个单词代表一行.通过这种方式,您可以方便地使用正则表达式搜索的强大功能,该搜索功能经过高度优化,可能会击败您可以针对此问题自行设计的任何数据结构.
这是针对此问题的Ruby代码:
def query(str, data)
r = Regexp.new("^#{str.gsub("?", ".")}$")
idx = 0
begin
idx = data.index(r, idx)
if idx
yield data[idx, str.size]
idx += str.size + 1
end
end while idx
end
start_time = Time.now
query("?r?te", File.read("wordlist.txt")) do |w|
puts w
end
puts Time.now - start_time
该文件wordlist.txt包含45425个单词(可在此下载).该程序的查询输出?r?te是:
brute
crate
Crete
grate
irate
prate
write
wrote
0.013689
因此,读取整个文件并查找其中的所有匹配项仅需37毫秒.它可以很好地适用于各种查询模式,即使Trie非常慢:
询问 ????????????????e
counterproductive
indistinguishable
microarchitecture
microprogrammable
0.018681
询问 ?h?a?r?c?l?
theatricals
0.013608
这对我来说足够快.
如果你想更快,你可以将wordlist拆分成包含相同长度的单词的字符串,并根据你的查询长度搜索正确的单词.用以下代码替换最后5行:
def query_split(str, data)
query(str, data[str.length]) do |w|
yield w
end
end
# prepare data
data = Hash.new("")
File.read("wordlist.txt").each_line do |w|
data[w.length-1] += w
end
# use prepared data for query
start_time = Time.now
query_split("?r?te", data) do |w|
puts w
end
puts Time.now - start_time
构建数据结构现在需要大约0.4秒,但所有查询的速度大约快10倍(取决于具有该长度的单词数):
?r?te 0.001112秒?h?a?r?c?l? 0.000852秒????????????????e 0.000169秒由于您已经更改了要求,因此您可以轻松扩展您的想法,只使用一个包含所有预先计算结果的大哈希表.但是,您可以依靠正确实现的哈希表的性能,而不是自己处理冲突.
在这里,我创建了一个大的哈希表,每个可能的查询映射到其结果列表:
def create_big_hash(data)
h = Hash.new do |h,k|
h[k] = Array.new
end
data.each_line do |l|
w = l.strip
# add all words with one ?
w.length.times do |i|
q = String.new(w)
q[i] = "?"
h[q].push w
end
# add all words with two ??
(w.length-1).times do |i|
q = String.new(w)
q[i, 2] = "??"
h[q].push w
end
end
h
end
# prepare data
t = Time.new
h = create_big_hash(File.read("wordlist.txt"))
puts "#{Time.new - t} sec preparing data\n#{h.size} entries in big hash"
# use prepared data for query
t = Time.new
h["?ood"].each do |w|
puts w
end
puts (Time.new - t)
输出是
4.960255 sec preparing data
616745 entries in big hash
food
good
hood
mood
wood
2.0e-05
查询性能为O(1),它只是哈希表中的查找.时间2.0e-05可能低于计时器的精度.运行1000次时,每次查询平均得到1.958e-6秒.为了更快地实现它,我将切换到C++并使用Google Sparse Hash,它非常节省内存并且速度很快.
以上所有解决方案都适用,对于许多用例而言应该足够好.如果你真的想要认真并且有很多空闲时间,请阅读一些好文章:
Ann*_*nna 24
鉴于目前的局限性:
我有两个可行的解决方案:
你可以使用哈希,你的单词是最多两个'？',而值是一个拟合单词列表.这个哈希将有大约100,000 + 100,000*6 + 100,000*5 = 1,200,000个条目(如果你有2个问号,你只需要找到第一个的位置......).每个条目都可以保存单词列表或指向现有单词的指针列表.如果你保存一个指针列表,我们假设平均少于20个单词匹配每个单词和两个'？',那么额外的内存小于20*1,200,000 = 24,000,000.
如果每个指针大小为4个字节,那么这里的存储器要求是(24,000,000 + 1,200,000)*4个字节= 100,800,000个字节〜= 96兆字节.
总结这个解决方案:
注意:如果要使用较小大小的哈希值,则可以,但最好是在每个条目而不是链接列表中保存平衡搜索树,以获得更好的性能.
该解决方案使用以下观察:
如果'？' 在这个词的最后,trie将是一个很好的解决方案.
trie中的搜索将搜索单词的长度,对于最后几个字母,DFS遍历将带来所有结尾.非常快速,非常精通内存的解决方案.
所以让我们使用这个观察,以便建立一个完全像这样的工作.
您可以考虑字典中的每个单词,作为以@结尾的单词(或字典中不存在的任何其他符号).所以"空间"这个词就是"空间@".现在,如果您使用"@"符号旋转每个单词,则会得到以下内容:
space@, pace@s, ace@sp, *ce@spa*, e@spac
(没有@作为第一个字母).
如果您将所有这些变体插入到TRIE中,您可以通过"旋转"您的单词轻松找到您在单词长度上搜索的单词.
示例:您想要找到所有符合's ?? ce'的单词(其中一个是空格,另一个是切片).你建立了这个词:s ?? ce @,然后旋转它以便？标志到底是什么时候.即'ce @ s ??'
所有的旋转变化都存在于trie中,特别是'ce @ spa'(用*标记为*).在找到开始之后 - 您需要以适当的长度检查所有延续,并保存它们.然后,你需要再次旋转它们,以便@是最后一个字母,而walla - 你拥有所有你想要的单词!
总结这个解决方案:
记忆消耗:对于每个单词,它的所有旋转都出现在trie中.平均而言,内存大小的*6保存在trie中.trie大小约为*3(只是猜测...)其中保存的空间.因此,此trie所需的总空间为6*3*100,000 = 1,800,000字〜= 6.8兆字节.
每次搜索的时间:
总而言之,它非常非常快,并且取决于字长*小常数.
第二种选择具有很好的时间/空间复杂性,并且是您使用的最佳选择.第二种解决方案存在一些问题(在这种情况下,您可能希望使用第一种解决方案):
Dat*_*ith 22
对我来说,这个问题听起来非常适合Trie数据结构.在整个字典中输入整个字典,然后查找单词.对于丢失的字母,您必须尝试所有子尝试,这应该相对容易使用递归方法.
编辑:我刚才在Ruby中编写了一个简单的实现:http://gist.github.com/262667.
安娜的第二个解决方案就是这个解决方案的灵感来源.
首先,将所有单词加载到内存中,并根据单词长度将字典分成几个部分.
对于每个长度,制作指向单词的指针数组的n个副本.对每个数组进行排序,以便在旋转一定数量的字母时按顺序显示字符串.例如,假设5个字母单词的原始列表是[plane,apple,space,train,happy,stack,hacks].然后你的五个指针数组将是:
rotated by 0 letters: [apple, hacks, happy, plane, space, stack, train]
rotated by 1 letter: [hacks, happy, plane, space, apple, train, stack]
rotated by 2 letters: [space, stack, train, plane, hacks, apple, happy]
rotated by 3 letters: [space, stack, train, hacks, apple, plane, happy]
rotated by 4 letters: [apple, plane, space, stack, train, hacks, happy]
(而不是指针,您可以使用标识单词的整数,如果这可以节省平台上的空间.)
要进行搜索,只需询问旋转模式所需的量,以便在结尾处显示问号.然后你可以在适当的列表中进行二进制搜索.
如果你需要找到?? ppy的匹配,你必须将它旋转2来制作ppy ??.因此,当旋转2个字母时,请查看按顺序排列的数组.快速二进制搜索发现"快乐"是唯一匹配.
如果你需要找到匹配的东西,你必须将它旋转4才能生成gth ??.因此,请查看数组4,其中二进制搜索发现没有匹配项.
只要它们全部出现在一起,无论有多少问号,这都有效.
所需的空间,除了字典本身:对于长度为N的话,这需要用于指针或整数(长度为N的字的次数N)的空间.
每次查找的时间:O(log n)其中n是适当长度的字数.
在Python中实现:
import bisect
class Matcher:
def __init__(self, words):
# Sort the words into bins by length.
bins = []
for w in words:
while len(bins) <= len(w):
bins.append([])
bins[len(w)].append(w)
# Make n copies of each list, sorted by rotations.
for n in range(len(bins)):
bins[n] = [sorted(bins[n], key=lambda w: w[i:]+w[:i]) for i in range(n)]
self.bins = bins
def find(self, pattern):
bins = self.bins
if len(pattern) >= len(bins):
return []
# Figure out which array to search.
r = (pattern.rindex('?') + 1) % len(pattern)
rpat = (pattern[r:] + pattern[:r]).rstrip('?')
if '?' in rpat:
raise ValueError("non-adjacent wildcards in pattern: " + repr(pattern))
a = bins[len(pattern)][r]
# Binary-search the array.
class RotatedArray:
def __len__(self):
return len(a)
def __getitem__(self, i):
word = a[i]
return word[r:] + word[:r]
ra = RotatedArray()
start = bisect.bisect(ra, rpat)
stop = bisect.bisect(ra, rpat[:-1] + chr(ord(rpat[-1]) + 1))
# Return the matches.
return a[start:stop]
words = open('/usr/share/dict/words', 'r').read().split()
print "Building matcher..."
m = Matcher(words) # takes 1-2 seconds, for me
print "Done."
print m.find("st??k")
print m.find("ov???low")
在我的计算机上,系统字典大909KB,除了存储字(指针是4个字节)之外,该程序还使用大约3.2MB的内存.对于这个字典,你可以通过使用2字节整数而不是指针来减少一半,因为每个长度的字数少于2 16个字.
测量:在我的机器上,m.find("st??k")运行0.000032秒,m.find("ov???low")0.000034秒,m.find("????????????????e")0.000023秒.
通过写出二进制搜索而不是使用class RotatedArray和bisect库,我将前两个数字降低到0.000016秒:快两倍.用C++实现它会使它更快.