高速文字列検索をするTRIEをRubyで使ってみた

トライ木を使用した高速な文字列検索をRubyで試してみました。 tyler/trieのサンプルコードを使用しています。

fast_trieをインストール

gem install fast_trie

コード

require 'trie'

trie = Trie.new

words = ['forestry', 'king', 'exculde', 'end', 'Meros']
words.each do |word|
  trie.add word
end

word = 'Meros raged.It was determined without fail that it was necessary to exclude king of Satol dishonest cruelty.'
node = trie.root

#TRIE木のルートからたどっていってterminalが見つかったら一致。
#terminalが見つかる前にたどる場所がなくなったら不一致。

word.split('').each do |char|
  break unless node.walk!(char)
  if node.terminal?
    puts "Found me a word: #{node.full_state}"
    break
  end
end

出力

Found me a word: Meros

結果

やってみて２つの欠点がわかりました。

1. 日本語の検索ができない
2. 文章の先頭からしか検索できない