Поиск, если множество Trie содержится в слове

Question

у меня есть 2 комплекта:

Set A: ['hi', 'there', 'hire', 'hih', 'hih543'] 

Set B: ['hihow', 'himan, 'fsdko45'] 

Теперь эти множества в действительности каждый из которых содержит близко к миллион элементов каждый.

Что мне нужно сделать, в двух словах, фильтр множество B, таким образом

1) Для каждого элемента множества В, найти все элементы множества А, которые являются префиксом для него.

Итак, в приведенном выше примере, когда я проверяю комплект A на hihow, я получаю 2 результата: hi и hih.

2) Скажем, у меня есть max_offset = 3. Для каждого из результатов, которые я получил в наборе A, я должен добавить [0,1,2,3], чтобы установить длину элементов A, и если ЛЮБОЙ результат равен заданной длине элемента B, верните true.

В этом примере предположим, что мы начинаем с hih, поэтому добавляю '1' к нему, добавляю '2' к нему, и получаю совпадение, hih.size + 2 == hihow.size. Вся операция возвращает true.

Теперь, как я могу сделать это таким образом, чтобы я не стал ждать часов для завершения этой операции? Один из подходов, который я решил использовать, состоит в том, чтобы сделать 1 набор попыток. Предположим, что мы создаем набор B a, который позволяет быстро искать.

Итак, теперь я перебираю элементы A и проверяю: для каких элементов множества B этот элемент является префиксом? Так что для 'hi' я бы получил ['hihow', 'himan']. Теперь я добавляю [0,1,2,3] в hi.size, и если результат соответствует размеру любого 1 элемента в массиве, этот элемент является совпадением.

Другим подходом было бы сделать множество A попыток и перебрать множество B, забрав в конце 0-3 символа. Так что скажите, что я принимаю hihow, я производю ['hihow', 'hiho', 'hih'] и проверяю все три, если какой-либо матч с множеством попыток. Да, есть совпадение, так что это возвращает true.

Боюсь, что в этом подходе я ничего не теряю с точки зрения правильности, поэтому я разместил его здесь. Кроме того, если у кого-то есть более простой/лучший способ сделать это, пожалуйста, дайте мне знать. Благодаря!

Answer 1

С помощью этого gem, похоже, было легче найти слова, начинающиеся с префикса, чем найти префиксы, содержащиеся в слове.

Trie делается из множества B. Для каждого матча, этот код проверяет, если суффикс имеет не более 3-х символов:

# gem install triez 
require 'triez' 

prefixes = ['hi', 'there', 'hire', 'hih', 'hih543'] 
words = ['hihow', 'himan', 'fsdko45'] 

word_trie = Triez.new 
words.each do |word| 
    word_trie[word] = 1 
end 

prefixes.each do |prefix| 
    suffixes = word_trie.search_with_prefix(prefix).select{|suffix, id| suffix.size <=3 } 
    suffixes.each do |suffix, id| 
    word = prefix + '|' + suffix 
    puts word 
    end 
end 

# => 
# hi|man 
# hi|how 
# hih|ow