사전을 사용하여 접미사 구분하기

Question

주어진 단어와 가능한 접미사 (약 1000 자)를 모두 구분해야합니다. 나는 딕트 사용에 대해 생각하고있다.

그래서 나는 접미어를 키로 사용할 것입니다 (추가 프로세스에서 필요한 접미사에 대한 몇 가지 추가 정보). 가능한 가장 긴 접미사가 4 글자 인 경우 모든 조합에 대해 딕트를 검색합니다. 예 : 주어진 단어 : 'abcdefg' 'g', 'fg', 'efg'및 'defg'에 대한 명령문을 검색합니다.

저는 약간의 연구를했으며 거의 ​​비슷한 용도를 찾지 못했습니다. 이것이 가능한 해결책 일 수 있습니까? 아니면 여기에 뭔가 빠졌습니까? 많이 appriciated 도움이됩니다.

Answer 1

이 솔루션은 좋은 소리 - 그것은 단어 당 몇 사전 룩 - 업, 그리고 사전 룩 - 업이 빠르다. 더 복잡한 솔루션 (trie 사용과 같은)이 여기에 가치가 있다고 생각하지 않습니다. 접미어 만 제거하기 위해 사전 대신 집합을 사용할 수도 있지만 각 접미어에 대한 추가 정보가 필요하기 때문에 사전이 자연스러운 선택 인 것으로 보입니다.

Answer 2

가장 간단한 (아마도 가장 빠르지는 않은) 방법은 목록에서 모든 일치 항목을 찾는 것입니다. 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 3

정확하게 유스 케이스를 이해하고 있는지 잘 모르겠습니다. 나는 그것이 당신이 접미사를 다루고 있다는 사실에 관한 것이고 그것을 탐지하기가 어렵다고 생각합니다.

일반적으로 (일반적으로 인덱싱 상황에서) 문자열을 접어 접미사로 사용하는 것이 일반적입니다. 그런 다음 역순 접미어 (따라서 접두어)의 정렬 된 목록에서 간단한 이진 검색을 수행 할 수 있습니다.

Answer 4

내가 원하는 것을 이해했다면 표준 lib에있는 re 모듈을 사용해야합니다.

문서 도구 현재 위치 :

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

여기 부사에 관한 예를 들어 있습니다 :

사전인가의 키로서 그들을 저장으로

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

, 나에게 좋은 것 같다. 특히, 당신이 신경 써서 접미사를 가진 단어에 대해 다른 처리를하고 싶다면.

Answer 5

Time Complexity of a dict을 참조하십시오. dict에 대한 조회 시간은 매우 빠릅니다 (평균 O (1)!). 이 구현의 경우, 가장 긴 접미어를 찾는 데 평균 시간 복잡도는 O (k^2)이며 k는 단어의 길이입니다. ''.join 연산 (문자열이 O (1) appendleft 연산을 지원하지 않으므로 역전 또는 문자열 분할과 유사한 O (n) 연산이 필요하기 때문에) k^2입니다. 당신이 문자열에서 접미사를 생성하고 :

이

>>> 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'