По заданному списку слов найдите все возможные слова, сгенерированные из слова, в удобной форме. - PullRequest
Новая
       8

По заданному списку слов найдите все возможные слова, сгенерированные из слова, в удобной форме.

0 голосов
/ 19 мая 2019

Я думаю об этом, скажем, у вас есть слово «палиндром».Из этого слова и из словаря возможных слов, которые я выучил («мой словарь»), вы можете сгенерировать: 

do
in
drone
mind
plan
line
role
lad
pad
drape
...

Теперь представьте, что мы делаем это программно, учитывая словарь в компьютерной форме (список слов в текстовом файле).Вопрос в том, как достаточно эффективно найти слова, которые можно сгенерировать из слова, для каждого слова .Таким образом, для каждого слова в словаре мы находим каждое слово, которое можно сгенерировать из него.

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

Наивный способ, которым я начинаю пытаться решить эту проблему, - это сначала загрузить все слова в хеш-таблицу, объект в JavaScript.Кажется, может быть, лучше положить их в три, но не уверен.Затем переберите каждое слово в хеш-таблице.Попробуйте сгенерировать все возможные комбинации букв всех возможных длин для данного слова.Я понятия не имею, как математически рассчитать, сколько это комбинаций, но кажется, что это много.Так что для «палиндрома» это 10 букв, но похоже на тонну комбинаций только для 10 буквенных комбинаций, не говоря уже о 9, 8, 7, 6 ....

Так интересно, как вы могли бы поступитьэто более эффективно.Я уверен, что кто-то уже нашел способ решить эту проблему.

Заметьте, это не вопрос домашней работы или интервью, мне просто интересно, как это сделать эффективно.

Ответы [ 2 ]

1 голос
/ 19 мая 2019

Это может быть хорошим приложением структуры данных trie . Это позволяет вам начать просматривать перестановки слова, выходя рано, если нет шансов, что слово будет в вашем словаре. Например, существует множество перестановок palindrome, которые начинаются с dp, но вы не будете рассматривать ни одну из них, потому что dp - это тупик в процессе.

Когда вы просматриваете palindrome, вы можете смотреть на mode. Вы добавите это в список найденных слов. В этом списке есть еще дети для mode, но нет для modep, modei и т. Д. Вы можете отрезать все эти ветви в своем поиске. Вы просто продолжите ветку, у которой есть дети, ведущие к таким словам, как model, modern.

Довольно просто превратить список слов в три с помощью словаря в python: 

trie = {}

with open('words.txt') as words:
    for word in map(lambda w: w.strip(), words):
        cur = trie
        for l in word:
            cur  = cur.setdefault(l, {})
        cur['word'] = True # defined if this node indicates a complete word

При наличии разумного списка слов в корневом словаре, вероятно, будет ключ для каждой буквы алфавита. Но он быстро становится меньше, когда вы спускаетесь. Например, при поиске небольшого списка слов trie['w'] будет иметь такие ключи, как ['a', 'e', 'h', 'i', 'o', 'r'], представляющие слова в вашем словаре, начиная с wa, we, ... и т. Д. trie['q'] может иметь только один ключ u, если у вас нет словаря с менее распространенными словами.

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

Учитывая созданное выше дерево и список из 3000 общих слов, он быстро находит 100 слов, рекурсивно сканируя дерево. Подсчет количества раз, когда внутренний цикл запускает цикл, показывает 2670 со словарем из 3000 слов - не так уж и плохо, учитывая, что в палиндроме есть 3,6 миллиона перестановок букв. Использование намного большего списка слов в /usr/share/dict/words, который содержит примерно 250 000 слов, требует 21543 циклов. Поиск «лоскутное одеяло» с большим списком запускался только 100 раз.

Вот код Python для обхода дерева для каждой допустимой перестановки. 

def findWords(word, trie = trie, cur = '', words = []):
    for i, letter in enumerate(word):
        if letter in trie:
            if 'word' in trie[letter]:
                words.append(cur + letter)
            findWords(word[:i] + word[i+1:], trie[letter], cur+letter, words )

    return words
words = findWords("palindrome")

Результат: 

['palm',
 'pale',
 'pain',
 'pair',
 'pan',
 'panel',
 'plan',

  ...

 'media',
 'ear',
 'earn',
 'end',
 'era']
1 голос
/ 19 мая 2019

Не проще ли сделать это наоборот?Просто просмотрите все слова в словаре, чтобы увидеть, может ли это слово быть сгенерировано из целевого слова.Таким образом, все, что нам нужно сделать, это вычитать буквы одну за другой, и как только письмо окажется пропущенным, мы можем объявить неудачу и перейти к следующему слову.Если мы начнем с преобразования целевого слова в пакет (посчитанный набор), наше обследование будет проходить довольно быстро.

Вот пример Swift.Мне понадобится пара служебных функций: 

func wordToCountedSet(_ s:String) -> NSCountedSet {
    return NSCountedSet(array: Array(s))
}
func canMake(_ s:String, from cs:NSCountedSet) -> Bool {
    let cs = cs.copy() as! NSCountedSet
    for letter in s {
        if !cs.contains(letter) {
            return false
        }
        cs.remove(letter)
    }
    return true
}

Рассмотрим эффективность NSCountingSet (есть ваш хэш) и тот факт, что canMake не удается рано и часто.

Чтобы проиллюстрировать,Представьте, что наш словарь состоит только из слов "дрон", "план", "планета" и "ксилофон".Я не буду перебирать словарь;Я просто покажу, что мы получаем правильный ответ: 

let cs = wordToCountedSet("palindrome")
canMake("drone", from:cs) // true
canMake("plan", from:cs) // true
canMake("planet", from:cs) // false
canMake("xylophone", from:cs) // false

С «планетой» мы не провалимся, пока не доберемся до конечного «т», но с «ксилофоном» мы провалим первыйписьмо.Другие должны вычесть каждую букву проверенного слова, чтобы преуспеть, но простого пути нет;несмотря на это, самое длинное, что может потребоваться для успеха - это количество букв в словарном слове.И все это очень быстро, потому что NSCountingSet хэшируется.Очевидно, что мы могли бы добавить несколько ярлыков (например, вы не можете сделать слово длиннее исходного слова), но это не совсем так.

...