Блог

Мне нужно создать функциональность, которая будет обрабатывать словарь (dictionary.txt файл). Цель состоит в том, чтобы найти все слова из шести букв, которые состоят из двух соединенных меньших слов, например:

 con   vex => convex
tail   or => tailor
we   aver => weaver
 

Конечно, в файле могут быть некоторые слова длиной не более 6 букв, но их можно легко отсеять простым методом:

 def cleanup_file
  file_data = File.read('dictrionary.txt').split

  file_data.reject! { |word| word.size < 6 }
end
 

Но теперь возникает проблема — как определить, состоят ли другие строки в массиве из двух соединенных меньших слов ?

[Править]

Образец dictionary.txt файл здесь

Думая только о псевдокодовом решении, но вы должны:

• Повторите каждую строку словаря и сохраните слова в 6 различных массивах по длине каждого слова.
  • Убедитесь, что все слова сокращены, нет дубликатов и все значения отсортированы, чтобы позже вы могли правильно использовать .bsearch их в массивах.
• Повторите массив длины 6 (например convex ) и найдите совпадение первого символа текущего слова в массиве длины 1 ( c для данного примера) и в массиве длины 5 ( onvex ). Если есть совпадение, сохраните слова.
  • Затем продолжайте искать совпадения в массивах длины 2 и длины 4 ( co и nvex соответственно) и сохраните совпадение.
  • Наконец, посмотрите обе части строки в массиве длины 3 ( con и vex ) и сохраните любое совпадение
  • Ищите следующую строку из 6 символов, пока не закончите.

Вероятно, есть лучшие способы решить эту проблему, как и в первой итерации вводя каждое слово в соответствующем массив с помощью .bsearch_index сортировки, а не вставлять дубликаты в той же итерации, но большая часть нагрузки будет на 2-й итерации и бинарного поиска работы в O(log n) раз, поэтому я предполагаю, что это должно работать достаточно быстро.

Предположим, что словарь выглядит следующим образом.

 dictionary = [
  "a", "abased", "act", "action", "animal", "ape", "apeman",
  "art", "assertion", "bar", "barbed", "barhop", "based", "be",
  "become", "bed", "come", "hop", "ion", "man"
]
 

Я предполагаю, что, как и большинство словарей, dictionary сортируется.

Сначала вычислите следующий хэш.

 by_len = dictionary.each_with_object({}) do |w,h|
  len = w.length
  (h[len] ||= []) << w if len < 7
end    
  #=> {1=>["a"],
  #    6=>["abased", "action", "animal", "apeman", "barbed",
  #        "barhop", "become"],
  #    3=>["act", "ape", "art", "bar", "bed", "hop", "ion", "man"],
  #    5=>["based"],
  #    2=>["be"],
  #    4=>["come"]}
 

Каждый ключ представляет собой длину слова (1-6), а каждое значение представляет собой массив слов dictionary , длина которых равна значению ключа.

Далее я определю вспомогательную функцию, которая возвращает true или false в зависимости от того, содержит ли данный массив слов ( list ) данное слово ( word ).

 def found?(list, word)
  w = list.bsearch { |w| w >= word }
  w amp;amp; w == word
end
 

Например:

 found?(by_len[3], "art")
  #=> true
found?(by_len[3], "any")
  #=> false
 

См. Массив#bsearch.

Теперь мы извлекаем интересующие нас слова:

 by_len[6].select { |w| (1..5).any? { |i|
  found?(by_len[i], w[0,i]) amp;amp; found?(by_len[6-i], w[i..-1]) } }
  #=> ["abased", "action", "apeman", "barbed", "barhop", "become"]