Как отсортировать все возможные слова из строки?

Question

Мне интересно, как выполнить эту задачу, возьмем эту строку, например, "thingsandstuff".

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

Цель состоит в том, чтобы найти допустимые английские слова в строке, не содержащей пробела.

Спасибо

Answer 1

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

O (мин (количество слов в словах, количество подстрок-комбинаций) * сравнение_ценка)

Итак, еще один подход к проблеме, основанный на Vinko, состоит в том, чтобы проиндексировать черт из словаря (например, для каждой работы в dict определить буквы в этом слове слова и т. д.). Это может значительно ускорить процесс. В качестве примера мы знаем, что целевая «королева» не может соответствовать «зебре» (без z!) (Или любому слову, содержащему z, r, b, a ...) и тому подобное. Кроме того, сохраните каждое слово в dict как отсортированную строку ('zebra' -> 'aberz') и выполните сопоставление "строка в строке" (самая длинная общая подстрока). 'eenuq' против 'abarz' (нет совпадений).

(Примечание: я предполагаю, что порядок букв в исходном слове не имеет значения - это «мешок с буквами», если они имеют значение, то отрегулируйте соответственно)

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

(Кроме того, я нырнул и сделал некоторые предположения, которых Алекс не сделал, поэтому, если они не правы, тогда закрой мне рот!)

Answer 2

Другая возможность - наоборот, вместо генерации подстрок из строки, взять все слова-кандидаты и сопоставить их с вашей строкой.

Вы можете хранить в результате (начало, конец) пары индексов слов в исходной строке.

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

Вот вам пример того, что я имею в виду

candidate = "thingsandstuffmydarlingpretty"
words = file('/usr/share/dict/words').read()
#This generator calls find twice, it should be rewritten as a normal loop
generate_matches = ((candidate.find(word),word) for word in words.split('\n')
                     if candidate.find(word) != -1 and word != '')

for match in generate_matches:
    print "Found %s at (%d,%d)" % (match[1],match[0],match[0] + len(match[1]))

Answer 3

Подход с использованием грубой силы, то есть проверка каждой подстроки, в вычислительном отношении невозможен даже для строк средней длины (строка длиной N имеет O(N**2) подстроки). Если нет достаточной жесткой границы длины струн, которая вас волнует, это плохо масштабируется.

Чтобы сделать вещи более осуществимыми, требуется больше знаний - вас интересуют перекрывающиеся слова (например, «вещи» и «песок» в вашем примере) и / или слова, которые оставляют неучтенными символы (например, «вещь» и «и» в вашем примере, оставляя промежуточные «s» запятыми), или вы хотите строгое разбиение строки на сопоставленные (не перекрывающиеся) слова без остатка?

Последнее было бы самой простой проблемой, потому что степени свободы резко падают - по существу, чтобы попытаться определить последовательность «точек разрыва», каждый между двумя смежными символами, которые разбили бы строку на слова. Если это так, нужно ли вам каждое возможное допустимое разделение (т. Е. Вам нужны оба"thing sand" и"вещи и"), или какое-либо одно действительное разделение будет делать, или Есть ли критерии, по которым ваш сплит должен быть оптимизирован?

Если вы проясните все эти вопросы, возможно, вам удастся оказать вам дополнительную помощь!

Answer 4

Норвинг написал отличную статью о том, как написать программу проверки орфографии в python.

http://norvig.com/spell-correct.html

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

после этого это базовый CS 101.

Answer 5

Это позволит определить, можно ли сформировать кандидата из букв в данном слове; предполагается, что word (но не candidate) сортируется до вызова.

>>> def match(candidate, word):

        def next_char(w):
            for ch in sorted(w):
                yield ch

        g = next_char(word)
        for cl in sorted(candidate):
            try:
                wl = g.next()
            except StopIteration:
                return False
            if wl > cl:
                return False
            while wl < cl:
                try:
                    wl = g.next()
                except StopIteration:
                    return False
                if wl > cl:
                    return False
        return True

>>> word = sorted("supernatural")
>>> dictionary = ["super", "natural", "perturb", "rant", "arrant"]
>>> for candidate in dictionary:
     print candidate, match(candidate, word)

super True
natural True
perturb False
rant True
arrant True

Когда я загружаю файл слов BSD (235 000+ слов) и запускаю его, используя plenipotentiary в качестве моего слова, я получаю около 2500 совпадений за полторы секунды.

Если вы собираетесь выполнять много поисков, неплохо бы удалить сортировку из next_char, создать словарь, основанный на отсортированной версии каждого слова -

d = dict([(sorted(word), word) for word in dictionary])

и выдайте результаты с помощью логики, подобной этой:

result = [d[k] for k in d.keys() if match(k, word)]

так что вам придется выполнять 250 000+ сортировок снова и снова.

Answer 6

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

Индекс словаря. Каждое слово (например, «привет») становится кортежем (ключ, данные), таким как («ehllo», «привет»). В ключе буквы отсортированы в алфавитном порядке.

Хорошие структуры данных индекса будут включать trie (он же цифровое дерево) или троичное дерево . Обычное двоичное дерево можно заставить работать. Хэш-таблица не будет работать. Я собираюсь взять дерево или тройное дерево. Примечание. Структура данных должна действовать как мультикарта (вам, вероятно, нужен связанный список сопоставленных элементов данных на каждом листе с сопоставлением ключей).

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

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

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

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

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

Сложность времени не сразу очевидна из-за возврата.

Answer 7

Код:

def all_substrings(val):
    return [val[start:end] for start in range(len(val)) for end in range(start + 1, len(val))]

val = "thingsandstuff"
for result in all_substrings(val):
    print result

Выход:

t
th
thi
thin
thing

[...]

tu
tuf
u
uf
f

Answer 8

Взгляните на в этом посте , в нем рассматривается одна и та же проблема, как в Python, так и в OCaml, с решением, основанным на нормализации строк, а не на грубом поиске.

Кстати, автоматический перевод удаляет отступы, поэтому, чтобы получить рабочий код Python, вы должны взглянуть на непереведенную испанскую версию (что на самом деле намного лучше, чем дрянной английский, созданный переводчиком Google ) ...

Edit:

Перечитывая ваш вопрос, теперь я понимаю, что вам могут понадобиться только те слова, которые не расшифрованы, верно? Если это так, вам не нужно делать все вещи, описанные в посте, просто:

maxwordlength = max(map(len, english_words))
for i in range(len(word)):
    for j in range(i+1, min(maxwordlength+i, len(word))):
         if word[i:j] in english_words:
             print word[i:j]

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

Answer 9

Я посмотрел на реализацию powerset. Слишком много возможностей.

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

from __future__ import with_statement
import collections

def word_dict(word):
    d = collections.defaultdict(int)
    for c in word:
        d[c] += 1
    return d

def compare_word_dict(dict_cand, cand):
    return all(dict_cand[k] <= cand[k] for k in dict_cand)


def try_word(candidate):
    s = word_dict(candidate)
    dictionary_file = r"h:\words\WORDs(3).txt"
    i = 0
    with open(dictionary_file) as f:
        for line in f:
            line = line.strip()
            dc = word_dict(line)
            if compare_word_dict(dc,s):
                print line
                i += 1
    return i


print try_word("thingsandstuff")

Я получаю 670 слов со своим словарем. Кажется немного маленьким. Занимает около 3 секунд на 200 тысяч слов в словаре.

Это работает для python 2.5 и выше из-за добавления collection.defaultdict . В python 3.1 было добавлено collection.Counter , которое работает как collection.defaultdict (int).

Answer 10

Что делать, если вы разбиваете его на слоги, а затем используете их для построения слов для сравнения со своим словарем. Это все еще метод грубой силы, но он наверняка немного ускорит процесс.