检查单词是否以某些前缀开头的最有效方法是什么？

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.bisect_left方法在前缀中查找小于时间复杂度中给定单词的最近单词：

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 2

在你的情况下，我猜散列将是有效的。你知道吗

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

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

Answer 3

平分比例尺更好。但是运行时不会比较前缀。（Runtime=O（nlog（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

如何阅读： 状态： 读取字符->；下一个状态，找到 ? =还有别的吗