Как наиболее эффективно проверить, начинается ли слово с определенных префиксов?

Question

Я хочу проверить, начинается ли перенос слов с префиксов в следующем наборе. Например, «соль».

prefixes = {
    'de-', 'dis-', 'il-', 'im-', 'ir-', 'inter-',
    'mid-', 'mis-', 'non-', 'pre-', 'pro-', 're-',
    'semi-', 'sub-', 'tele-', 'trans-',
    'un-', 'e-'
}

Вот мой код:

def prefix(word):
    match = re.match(r"[a-z]+-",word)
    if match:
        if match.group() in prefixes:
            return True
word = "e-mail"
print(prefix(word))

Answer 1

Bisect весы лучше, чем это.Но среда выполнения не смотрит на сравнение префиксов.(Время выполнения = O (n log (n)), если вы рассматриваете аналогичные префиксы для префиксов. Но для примера это лучшее решение.)

---

Самый эффективный способ - использовать толькопервые n символов (с префиксом n = макс. длины) [необязательно: конечный автомат может сделать это и для вас] и передать каждую из этих букв конечному автомату.

Этот конечный автомат должен решитькакие префиксы все еще можно получить.

E.g. to be tested: "prefix" with your list of prefixes
You start with "" -> everything is possible
You read the "p" -> {pro, pre} are possible prefixes now
You read the "r" -> still the same, both start with "pr"
You read the "e" -> pro is not possible and pre has been found.

---

Можно создать конечный автомат из списка префиксов.Но я не буду вдаваться в подробности.

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

An example:
Let me add prof to your list of prefixes.

0:
p -> 1
? -> to be added, there are more prefixes

1:
r -> 2
? -> terminate, nothing found

2:
e -> terminate, found pre
o -> 3, found pro
? -> -1

3:
f -> terminate, found pro and prof
? -> terminate, found pro

Как читатьthis: state: читать символ -> следующее состояние, найдено?= все остальное

Answer 2

Сначала можно отсортировать префиксы, чтобы можно было использовать метод bisect.bisect_left, чтобы найти самое близкое слово в префиксах, которое меньше заданного слова в O (log n) сложность времени:

from bisect import bisect_left
prefixes = sorted(prefixes)
def prefix(prefixes, word):
    i = bisect_left(prefixes, word)
    if i and word.startswith(prefixes[i - 1]):
        return prefixes[i - 1]
    raise ValueError("No prefix found for '%s'." % word)

так что:

print(prefix(prefixes, 'non-word'))
print(prefix(prefixes, 'tele-video'))
print(prefix(prefixes, 'e-mail'))

выходы:

non-
tele-
e-

Answer 3

В вашем случае, я думаю, хеширование будет эффективным.

m=set()
for x in prefixes:
    m.add(x.split(‘-‘)[0])

return word.split(‘-‘)[0] in m