Разделение суффиксов с помощью словаря

Question

Мне нужно отделить все возможные суффиксы (около 1000) от заданного слова. Я думаю об использовании диктанта.

При этом у меня будут суффиксы в качестве ключей (и некоторая дополнительная информация о суффиксах в качестве значений, необходимых в дальнейшем процессе). Если самый длинный суффикс составляет 4 буквы, я бы искал в диктанте все возможные комбинации. Например: Учитывая слово: «abcdefg», я бы искал в словаре слова «g», «fg», «efg» и «defg».

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

Answer 1

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

Answer 2

См. Сложность времени дикта . Время поиска для dict довольно быстро (в среднем O (1)!). Для этой реализации средняя сложность времени для нахождения самого длинного суффикса будет O (k ^ 2), где k - длина вашего слова. Это k ^ 2 из-за операции ''.join (потребовалась бы аналогичная операция O (n), например, перевернутая или нарезка строк, поскольку строки не поддерживают операцию аппендифмента O (1)).

Простой способ сделать это (проверено на python 3):

>>> from collections import deque
>>> word = "antidisestablishmentarianism"
>>> suffixes = {'ism': 3, 'anism': 6, 'ment': 4, 'arianism': 12}
>>> suffix = deque()
>>> longest = None
>>> for char in reversed(word):
...     suffix.appendleft(char)
...     suf = ''.join(suffix)
...     if suf in suffixes:
...         longest = suf
...
>>> longest
'arianism'

Answer 3

Самый простой (вероятно, не самый быстрый) способ - найти все совпадения в списке.С 1000 предметов у вас не должно быть особых проблем с производительностью.

>>> sufx = ['foo', 'bar']
>>> [s for s in sufx if 'bazbar'.endswith(s)]
['bar']
>>>[s for s in sufx if 'bazbaz'.endswith(s)]
[]
>>> [s for s in sufx if 'bazfoo'.endswith(s)]
['foo']

Answer 4

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

Документы здесь:

http://docs.python.org/library/re.html#module-re

Естьпример относительно наречий здесь:

http://docs.python.org/library/re.html#finding-all-adverbs

Что касается хранения их в качестве ключей в диктовке, мне кажется, это хорошо.Особенно, если вы хотите выполнить какую-то другую обработку для слов с суффиксами, которые вам нужны.

Answer 5

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

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