Ходить по строкам, чтобы угадать имя по электронной почте на основе словаря имен?

Question

Допустим, у меня есть словарь имен (огромный файл CSV).Я хочу угадать имя из электронного письма, которое не имеет очевидных парсинговых точек (., -, _).Я хочу сделать что-то вроде этого:

  dict = ["sam", "joe", "john", "parker", "jane", "smith", "doe"]
  word = "johnsmith"
  x = 0
  y = word.length-1
  name_array = []
  for i in x..y
     match_me = word[x..i]
     dict.each do |name|
       if match_me == name
         name_array << name
       end
     end
  end   

  name_array
  # => ["john"]

Неплохо, но я хочу, чтобы "Джон Смит" или ["Джон", "Смит"]

Вдругими словами, я рекурсивно перебираю слово (т. е. неразобранную строку электронной почты "johndoe@gmail.com"), пока не найду совпадение в словаре. Я знаю: это невероятно неэффективно. Если есть намного более простой способ сделать это, я весь в ушах!

Если нет лучшего способа сделать это, то покажите мне, как исправить приведенный выше пример, поскольку он страдает двумя основными недостатками: (1) как мне установить длину цикла (см. Проблему поиска«i» ниже) и (2) как увеличить «x» в приведенном выше примере, чтобы можно было циклически проходить все возможные комбинации символов, заданные произвольной строкой?

Проблема определения длины цикла "i":

  for an arbitrary word, how can we derive "i" given the pattern below?

  for a (i = 1)
  a

  for ab (i = 3)
  a
  ab
  b

  for abc (i = 6)
  a
  ab
  abc
  b
  bc
  c

  for abcd (i = 10)
  a
  ab
  abc
  abcd
  b
  bc
  bcd
  c
  cd
  d

  for abcde (i = 15)
  a
  ab
  abc
  abcd
  abcde
  b
  bc
  bcd
  bcde
  c
  cd
  cde
  d
  de
  e

Answer 1

r = /^(#{Regexp.union(dict)})(#{Regexp.union(dict)})$/
word.match(r)
=> #<MatchData "johnsmith" 1:"john" 2:"smith">

Для построения регулярного выражения может потребоваться некоторое время, но оно быстро работает.

Answer 2

Смею предложить решение грубой силы, которое не очень изящно, но все же полезно в случае, если

• у вас есть большое количество предметов (создание регулярного выражения может быть проблемой)
• строка для анализа не ограничена двумя компонентами
• вы хотите получить все разбиения строки
• вы хотите только полный анализ строки, который охватывает от ^ до $.

Из-за моего плохого английского я не мог найти длинное личное имя, которое можно разделить несколькими способами, поэтому давайте проанализируем фразу:

word = "godisnowhere"

Словарь:

@dict = [ "god", "is", "now", "here", "nowhere", "no", "where" ]

@lengths = @dict.collect {|w| w.length }.uniq.sort

Массив @lengths добавляет небольшую оптимизацию алгоритма, мы будем использовать его для сокращения подслов длины, которых нет в словаре, без фактического выполнения поиска в словаре.Массив отсортирован, это еще одна оптимизация.

Основной частью решения является рекурсивная функция, которая находит начальное подслово в данном слове и перезапускает для подслово хвоста.

def find_head_substring(word)

  # boundary condition:
  # remaining subword is shorter than the shortest word in @dict
  return []  if word.length < @lengths[0]

  splittings = []

  @lengths.each do |len|
    break  if len > word.length

    head = word[0,len]

    if @dict.include?(head)
      tail = word[len..-1]

      if tail.length == 0
        splittings << head
      else
        tails = find_head_substring(tail)
        unless tails.empty?
          tails.collect!{|tail| "#{head} #{tail}" }
          splittings.concat tails
        end
      end
    end
  end

  return splittings
end

Теперь посмотрим, как это работает

find_head_substring(word)
=>["god is no where", "god is now here", "god is nowhere"]

Я не тестировал его подробно, поэтому заранее прошу прощения:)

Answer 3

Если вы просто хотите, чтобы совпадения совпадений в вашем словаре:

dict.select{ |r| word[/#{r}/] }
=> ["john", "smith"]

Вы рискуете получить слишком много запутанных субхитов, поэтому вы можете отсортировать словарь, чтобы длинные имена были первыми:

dict.sort_by{ |w| -w.size }.select{ |r| word[/#{r}/] }
=> ["smith", "john"]

Вы по-прежнему будете сталкиваться с ситуациями, когда более длинное имя имеет более короткую подстроку, следующую за ним, и получает несколько попаданий, поэтому вам нужно найти способ отсеять их. Вы можете иметь массив имен и другое из фамилий и взять первый возвращенный результат сканирования для каждого, но учитывая разнообразие имен и фамилий, это не гарантирует 100% точности и все равно соберет некоторые плохие результаты.

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

Answer 4

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

pattern = Regexp.union(dict)
matches = []
while match = word.match(pattern)
  matches << match.to_s # Or just leave off to_s to keep the match itself
  word = match.post_match
end
matches

Answer 5

Я не уверен, что вы делаете с i, но не так ли просто, как:

dict.each do |first|
    dict.each do |last|
        puts first,last if first+last == word
    end
end