Ruby left-> right индексированная строка коллекции

Question

Я ищу коллекцию ruby, которая поддерживает индекс left-> right для строк, похожих на любой индекс строки базы данных. Целью было бы быстрый поиск строк по префиксу этой строки. Я знаю, что это можно сделать вручную, используя дерево, но я ищу встроенный метод ruby ​​...

Например, при наличии коллекции, содержащей слово «помидор», поиск по «тому» будет производить это слово без необходимости полного сканирования коллекции.

Answer 1

Ну, есть 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"}

Answer 2

Как насчет использования сортировки по предварительно отсортированному списку для эффективного достижения начальной точки для сравнения, а затем выполнения регулярного выражения для нескольких следующих слов?

# 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" из отсортированного списка, а сопоставление регулярному выражению предпринимается только пять раз (четыре успеха и одна ошибка), чтоне должно быть большой нагрузки.И соответствие с использованием регулярных выражений не зависит от размера списка.