接尾辞配列を構築する前にPythonで文字列のセンチネルの終わりを指定する

Question

私は、接尾辞配列を利用して最も長い共通部分文字列を見つけるアルゴリズムをhttp://portal.acm.org/citation.cfm?id=1813708に実装しています。アルゴリズムは、与えられた文字列と、センチネルと呼ばれる文字列セパレータとの連結である文字列のサフィックス配列を作成することを含む。例えば、文字列a、b、cが与えられた場合、新しい文字列dが作成されます。この文字列dは$ 1b、$ 2c $ 3です。$ 1、$ 2、$ 3は各文字列の終わりを示すセンチネル文字です。センチネル文字は、a、b、およびcの他のすべての文字よりも一意で、辞書編集的に小さくなければなりません。

私の質問は、Pythonでのセンチネル文字の表現を中心にしています。 a、b、cがASCII文字列の場合、私はこれらの文字列をUTF-8に変換し、その範囲を0-127から高い範囲にシフトする必要があると考えています。弦。それが合理的だと思われる場合、Pythonの文字をN-127 + Nのように再マッピングするための最も効率的なメカニズムは何ですか？ここでNは文字列の数です。

Answer 1

私はあなたがトークナイザを使用して、整数で、各文字列に置き換えるべきだと思います。その後、センチネルのために、多くの整数が残ります。おそらく、小さな整数ではなく、大きな整数をセンチネルとして使うほうが便利でしょう。プリントアウトのために、あなたが望むどんなUnicode文字でも使うことができます。同じ文字を使うこともできます。

山本を実装しています&教会？もしそうなら、あなたが始める前にいくつかのより新しい文献を見てください。私は、AbouelhodaらのExtended Suffix ArrayとKim、Kim & Park、Linearized Suffix Treesを勧めます。コンビナトリアルが好きなら、Schürmann、Klaus-Bernd、理論と実践の接尾辞配列を見てください。

また、特殊な接尾辞ソートアルゴリズムではなく、3方向基数クイックソートをお勧めします。コーパスに冗長性がある場合は、サフィックスソートアルゴリズムだけが必要です。しかし、これらの冗長性は不要で、あなたの統計を台無しにするでしょう。

そして、あなたが何か面白いものを作れば、私は

デールGerdemann

Answer 2

これは、Unicode（UTF-8ではなく）文字列を使用して行うことができます。 Python 3では、すべての文字列がUnicodeですが、Python 2では、接頭辞uが必要です（つまり、"hello"はUnicodeではなく、u"world"です）。

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

Pythonの3のために、これはわずかに簡単になります：

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