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

Question

Допустим, у меня есть слово "CAT".Эти слова отличаются от "CAT" на одну букву (не полный список)

• CUT
• CAP
• PAT
• FAT
• COT
• и т. Д.

Существует ли элегантный способ создать это?Очевидно, что один из способов сделать это - перебор.

псевдо-код:

while (0 to length of word)
    while (A to Z)
        replace one letter at a time, and check if the resulting word is a valid word

Если бы у меня было слово из 10 букв, цикл выполнялся бы 26 * 10 = 260 раз.

Есть ли лучший, элегантный способ сделать это?

Answer 1

Дан список слов, например с

words = set(line.strip().lower() for line in open('/usr/share/dict/words'))

Вы можете создать и индексировать слова с "подстановочными знаками", где вы заменяете каждый символ слова на подстановочный знак (скажем, "?"), Так что, например, "gat" и "fat" оба индексируются как "? At «:

def wildcard(s, idx):
    return s[:idx] + '?' + s[idx+1:]

def wildcarded(s):
    for idx in xrange(len(s)):
        yield wildcard(s, idx)

# list(wildcarded('cat')) returns ['?at', 'c?t', 'ca?']

from collections import defaultdict
index = defaultdict(list)

for word in words:
    for w in wildcarded(word):
        index[w].append(word)

Теперь, если вы хотите найти все слова, которые отличаются на одну букву от слова "кошка", просто найдите слова "? At", "c? T" и "ca?" и объединить результаты:

def near_words(word):
    ret = []
    for w in wildcarded(word):
        ret += index[w]
    return ret

print near_words('cat')
# outputs ['cat', 'bat', 'zat', 'jat', 'kat', 'rat', 'sat', 'pat', 'hat', 'oat', 'gat', 'vat', 'nat', 'fat', 'lat', 'wat', 'eat', 'yat', 'mat', 'tat', 'cat', 'cut', 'cot', 'cit', 'cay', 'car', 'cap', 'caw', 'cat', 'can', 'cam', 'cal', 'cad', 'cab', 'cag']
print near_words('stack')
# outputs ['stack', 'stack', 'smack', 'spack', 'slack', 'snack', 'shack', 'swack', 'stuck', 'stack', 'stick', 'stock', 'stank', 'stack', 'stark', 'stauk', 'stalk', 'stack']

Если максимальная длина слова составляет L, а количество слов - N, индекс состоит из O(NL) указателей, а алгоритм поиска выполняется во времени O(L + number of results).

Если вы хотите найти все слова, которые отличаются K буквами вместо 1, этот подход не очень хорошо обобщает, но это очень сложная проблема в полной общности (это проблема поиска соседей в пространствах Хэмминга).

Answer 2

1. Подумайте, каковы ваши требования к производительности.

2. Реализуйте в точности так, как вы описали выше.

3. Время и посмотреть, если вы уже соответствуете этим требованиям.

4. Оптимизация только в случае необходимости (и я готов поспорить, что в этом нет необходимости, поскольку 260 просмотров в хэш-таблице слов, которые помещаются в ОЗУ, не такие медленные.)

Answer 3

Размер словаря для человеческого языка и длина слова крошечные (~ 10 ** 5 и ~ 100), поэтому подход грубой силы подойдет, если измерения не показывают иное в вашем случае:

#!/usr/bin/env python
import string

ALL_WORDS = set(open('/usr/share/dict/words').read().lower().split())
ALPHABET = string.ascii_lowercase

def known(words): return set(w for w in words if w in ALL_WORDS)

def one_letter(word):
    # http://norvig.com/spell-correct.html
    splits = ((word[:i], word[i:]) for i in range(len(word) + 1))
    replaces  = (a + c + b[1:] for a, b in splits for c in ALPHABET if b)
    return set(replaces)

from pprint import pprint
pprint(known(one_letter("cat")))

Выход

set(['bat',
     'cab',
     'cad',
     'cal',
     'cam',
     'can',
     'cap',
     'car',
     'cat',
     'caw',
     'cot',
     'cut',
     'eat',
     'fat',
     'hat',
     'mat',
     'nat',
     'oat',
     'pat',
     'rat',
     'sat',
     'tat',
     'vat'])

Answer 4

Для: l = длина слова, w = количество слов в списке слов:

Ваш алгоритм O (l. (L log w)) для списка слов дерева, plus theстоимость создания списка слов в первую очередь (это O (w log (w))) (я предполагаю, что дерево здесь, вы можете переделать это с помощью хэша, если хотите).

Это O (lw)

Как уже предлагает другой ответ, вас не волнует, что слово содержит a, b или z вместо символа, который вы хотите изменить, вы просто заботитесь, что это не буква, которую вы началис.Так что протестируйте одну комбинацию, которую вы не хотите, а не все комбинации, которые могли бы сделать.

Итак:

for(each candidate word from the wordlist) {
  difference = 0
  for(each letter in your original word) {
    does it match? if not, difference++
  }
  if difference = 1, store the candidate word as a solution
}

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

Answer 5

Вам понадобится словарь допустимых слов для проверки, иначе проблема не в генерировании «слов», а скорее «строк». Многие из них доступны бесплатно онлайн, или, если вы работаете в Linux, большинство дистрибутивов имеют файлы словарей в /usr/share/dict/.

Есть два подхода:

1. Для каждой буквы в слове замените ее на все остальные 25 символов и проверьте, есть ли она в словаре. Используйте хеш-таблицу для хранения словарных слов для эффективного запроса. Вам нужно всего лишь заполнить хеш-таблицу словами той же длины, что и искомое слово. Это будет O (MN + 25N) = O (MN), где M - количество слов длины N в вашем словаре, а N - длина вашего слова.

2. Для каждого слова из словаря, длина которого равна вашему поисковому слову, проверьте, сколько символов отличается. Это будет O (MN).

Хотя оба попадают в один и тот же класс сложности, последний отбрасывает член O (25N) и накладные расходы, связанные с хеш-таблицей.

Answer 6

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

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

По моим оценкам, обработка 20000 слов, обрабатываемых не менее 30 секунд, займет не более 11 минут.

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

Большой объем памяти, но сверхбыстрый - и если вы беспокоитесь о производительности 260 просмотров, вы должны иметь дело с десятками тысяч слов, и такое решение, вероятно, будет лучшим, которое вы получите.

Answer 7

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

Более быстрое решение, если словарь статичен и нужно проверить много слов: создайте матрицу букв.Строки - первая буква в слове, столбцы - вторая буква в слове.Клетки - это список слов, которые начинаются с данной первой и второй буквы.Если вы хотите найти похожие слова для данного слова, выполните итерацию по одной строке, а затем по одному столбцу.Если не в пересекающейся ячейке, все остальные буквы каждого повторяющегося слова должны совпадать.На пересекающейся ячейке одна буква должна отличаться.

Answer 8

Если строки всегда совпадают по длине, одним способом будет удалить по одной букве за раз и сравнить результат по обеим строкам, 10 символов будут 10 циклами.

Answer 9

В любом случае вам нужно будет перебрать все буквы, чтобы проверить это. Но другой подход заключается в проверке словаря на наличие слов, который соответствует маске «AT, C» T, CA ». (где? может быть каждый символ)