접미사 배열을 구성하기 전에 파이썬에서 문자열 센티널의 끝 지정

Question

나는 가장 긴 공통 부분 문자열을 찾기 위해 접미어 배열을 사용하는 http://portal.acm.org/citation.cfm?id=1813708에 알고리즘을 구현하고 있습니다. 알고리즘은 지정된 문자열 집합과 센티넬이라는 문자열 구분 기호를 연결 한 문자열에 대한 접미어 배열을 만드는 작업과 관련됩니다. 예를 들어, 문자열 a, b 및 c가 주어지면 $ 1b $ 2c $ 3 인 새 문자열 d가 만들어집니다. $ 1, $ 2, $ 3은 각 문자열의 끝을 표시하는 센티널 문자입니다. 센티넬 문자는 a, b 및 c의 다른 모든 문자보다 고유하고 사전 식이어야합니다.

내 질문은 파이썬에서 센티넬 문자 표현을 중심으로 이루어집니다. a, b 및 c가 ASCII 문자열 인 경우 해당 문자열을 UTF-8로 변환하고 해당 범위를 0-127에서 높은 범위로 변경해야 할 수도 있습니다. 따라서 사전 적으로 사용할 수있는 문자가 현. 이것이 합리적이라면 파이썬에서 문자를 다시 매핑하는 가장 효율적인 메커니즘은 무엇입니까? 범위는 N-127 + N입니다. 여기서 N은 제공된 문자열의 수입니까?

Answer 1

난 당신이 토크 나이를 사용하고 정수로 각 문자열을 대체한다고 생각합니다. 그 다음 센티넬에게는 많은 정수가 남을 것입니다. 아마도 더 큰 정수를 작은 정수보다는 센티넬으로 사용하는 것이 더 편리 할 것입니다. 인쇄물의 경우 원하는 유니 코드 문자를 사용할 수 있으며 모든 문자에 동일한 문자를 사용할 수 있습니다.

Yamamoto를 구현하고 있습니까 & Church? 그렇다면 시작하기 전에 새로운 문학을 살펴보십시오. Abouelhoda 외에도 Extended Suffix Array와 Kim, Kim & Park, Linearized Suffix Trees를 추천합니다. 그리고 만약 당신이 조합론을 좋아한다면, Schürmann, Klaus-Bernd, 이론과 실습의 서 픽스 배열을보십시오.

또한 특수 접미사 정렬 알고리즘과 달리 3 방향 기수 정렬을 권장합니다. 코퍼스의 중복시 접미사 정렬 알고리즘 만 필요합니다. 그러나 이러한 중복은 불필요하며 통계를 망칠 것입니다.

그리고 당신은 흥미있는 일을 할 경우, 나는

데일 Gerdemann

Answer 2

유니 코드 (UTF-8 아님) 문자열을 사용하여이 작업을 수행 할 수 있습니다. 파이썬 3에서는 모든 문자열이 유니 코드이지만 파이썬 2에서는 u 접두어가 필요합니다 (즉, "hello"은 유니 코드가 아니지만 u"world" 임).

>>> s = u"string one" 
>>> N = 3 
>>> "".join(unichr(ord(x) + N) for x in s) 
u'vwulqj#rqh' 

파이썬 3의 경우,이 약간 더 간단 할 것이다 :

>>> s = "string one" 
>>> N = 3 
>>> "".join(chr(ord(x) + N) for x in s) 
'vwulqj#rqh'