私は、任意のデータベース文字列インデックスに似た文字列に左→右インデックスをサポートするルビコレクションを探しています。その目的は、その文字列のプレフィックスによって文字列を高速に検索することです。私はこれが木を使って手で行うことができることを知っていますが、私は組み込みのルビーメソッドを探しています...Ruby left-> right indexed string collection
例えば、 "tom"という単語を含むコレクションがあれば、 "tom"コレクションの全面的なスキャンを行うことなく、その言葉を生み出します。
まあ、abbrevあり：
require 'abbrev'
wordlist = [
"smooth", "snail", "sneak", "snooze", "snore", "snow", "snowball",
"snowflake", "snowman", "soak", "soap", "sofa", "soil", "someone", "somewhere"
].abbrev
：
{"smoot"=>"smooth", "smoo"=>"smooth", "smo"=>"smooth", "sm"=>"smooth",
"snai"=>"snail", "sna"=>"snail", "snea"=>"sneak", "sne"=>"sneak",
"snooz"=>"snooze", "snoo"=>"snooze", "snor"=>"snore", "snowbal"=>"snowball",
"snowba"=>"snowball", "snowb"=>"snowball", "snowflak"=>"snowflake",
"snowfla"=>"snowflake", "snowfl"=>"snowflake", "snowf"=>"snowflake",
"snowma"=>"snowman", "snowm"=>"snowman", "sof"=>"sofa", "soi"=>"soil",
"someon"=>"someone", "someo"=>"someone", "somewher"=>"somewhere",
"somewhe"=>"somewhere", "somewh"=>"somewhere", "somew"=>"somewhere",
"smooth"=>"smooth", "snail"=>"snail", "sneak"=>"sneak", "snooze"=>"snooze",
"snore"=>"snore", "snow"=>"snow", "snowball"=>"snowball", "snowflake"=>"snowflake",
"snowman"=>"snowman", "soak"=>"soak", "soap"=>"soap", "sofa"=>"sofa",
"soil"=>"soil", "someone"=>"someone", "somewhere"=>"somewhere"}
うーん、それほどそれを考えたことはありません。これはうまくいくでしょうが、バイナリ検索ツリーに裏打ちされている可能性のあるものよりも（メモリ使用量に関して）効率が悪いです...他に何も来なければ受け入れます。 –
何それから、効率的に比較するための出発点を達成するために事前にソートされたリストに対するソートの使用についていくつかの言葉のために正規表現マッチをしていますか？
# Using steenslag's list
$list = %w[
smooth snail sneak snooze snore snow snowball
snowflake snowman soak soap sofa soil someone somewhere
].sort!
def left_match str
return [] unless i = $list.index{|w| str <= w}
matches = []
re = /\A#{str}/
while w = $list[i] and w =~ re
matches.push(w)
i += 1
end
matches
end
この例：
p left_match("snow")
はここ
["snow", "snowball", "snowflake", "snowman"]
を返します、indexは、ソートされたリストから"snow"を見つけるために使用され、かつ正規表現マッチは唯一の5倍（4成功をしようとしています、1つの失敗）、それはあまり負荷がかかるべきではありません。正規表現を使ったマッチは、リストのサイズの影響を受けません。
別の言葉で例を挙げて明確にすることはできますか？ – Linuxios
インデックスを持つ文字列型の1列 'name'を持つdbテーブルがあるかのように同じです。次のようなクエリを実行した場合： "select * from table where name 'tom％'"これはインデックスのおかげで非常に効率的です。典型的なハッシュや配列は、あなたにこのタイプのインデックスを与えません... –