Сочетание клавиш для фраз поиска в реальном времени

Question

В результате поиска в реальном времени на сайте у меня есть набор строк, таких как:

[
  'how',
  'how do i',
  'how do i cancel my',
  'how do i cancel my account',
  'where is',
  'where is the',
  'where is the analytics',
  'where is the analytics page'
]

Мне нужно применить алгоритм редактирования расстояния, который оставит мне только два «финала» ”Фразы:

[
  'how do i cancel my account',
  'where is the analytics page'
]

Буду признателен за любые предложения по реализации.

UPD: это будет использоваться для поисковой аналитики, поэтому потенциально могут быть обработаны десятки тысяч записей. .

UPD2: я закончил с этим подходом, который дает мне стабильную оценку >0.8 для фильтрации окончательных запросов. Мне любопытно услышать об альтернативах. Алгоритм подобия Джаро-Винклера *1013* кажется наиболее подходящим, потому что он дает больший приоритет ведущим символам над трейлингом.

require 'edits'

values = [
  'how',
  'how do i',
  'how do i cancel my',
  'how do i cancel my account',
  'where is',
  'where is the',
  'where is the analytics',
  'where is the analytics page'
]

values.map(&:strip).uniq
  .each_cons(2)
  .map do |seq|
    [
      seq.first,
      seq.last,
      Edits::JaroWinkler.similarity(seq.first, seq.last)
    ]
  end

["how", "how do i", 0.8541666666666666]
["how do i", "how do i cancel my", 0.888888888888889]
["how do i cancel my", "how do i cancel my account", 0.9384615384615385]
["how do i cancel my account", "where is", 0.47243589743589737]
["where is", "where is the", 0.9333333333333333]
["where is the", "where is the analytics", 0.9090909090909091]
["where is the analytics", "where is the analytics page", 0.962962962962963]

Answer 1

Следующий код должен удалить префиксы.

require 'set'

suggestions = Set.new([
  'how',
  'how do i',
  'how do i cancel my',
  'how do i cancel my account',
  'where is',
  'where is the',
  'where is the analytics',
  'where is the analytics page'
])
phrases = suggestions.each do |a|
  suggestions.delete_if {|b| a != b && a.start_with?(b) }
end

phrases.to_a

Обратите внимание, что приведенный выше код не подходит для больших массивов. Но я думаю, что вы не получите более 15 или 20 предложений (с префиксами) из вашего приложения.

Ссылка: Set # delete_if

Надеюсь, это поможет.