1

http://portal.acm.org/citation.cfm?id=1813708でアルゴリズムを実装しています。このアルゴリズムは、接尾辞配列を利用して最長の共通部分文字列を見つけます。アルゴリズムには、指定された文字列のセットをセンチネルと呼ばれる文字列区切り文字で連結した文字列のサフィックス配列を構築することが含まれます。たとえば、文字列 a、b、c が与えられた場合、新しい文字列 d が作成されます。これは a$1b$2c$3 で、ここで $1、$2、$3 は各文字列の末尾を示す番兵文字です。センチネル文字は一意で、a、b、c の他のすべての文字よりも辞書順で少なくなければなりません。

私の質問は、Python でのセンチネル キャラクターの表現に関するものです。a、b、および c が ASCII 文字列の場合、これらの文字列を UTF-8 に変換し、それらの範囲を 0 ～ 127 からより高い範囲にシフトして、使用可能な文字が、弦。それが合理的であると思われる場合、範囲が N-127+N (N は提供される文字列の数) になるように Python で文字を再マッピングするための最も効率的なメカニズムは何ですか?

4

2 に答える 2

1

これは、Unicode (UTF-8 ではない) 文字列を使用して行うことができます。uPython 3 ではすべての文字列が Unicode ですが、Python 2 ではプレフィックスが必要です(つまり"hello"、 は Unicode ではなく、Unicodeu"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'
于 2011-02-10T00:09:40.157 に答える
0

トークナイザーを使用して、各文字列を整数に置き換える必要があると思います。次に、センチネルの場合、多くの整数が残ります。おそらく、小さな整数よりも大きな整数をセンチネルとして使用する方が便利です。プリントアウトには、必要な Unicode 文字を使用できます。また、それらすべてに同じ文字を使用することもできます。

山本＆チャーチを実装していますか？もしそうなら、始める前にいくつかの新しい文献を見てください。Aboelhoda らの Extended Suffix Array と Kim、Kim & Park の Linearized Suffix Trees をお勧めします。組み合わせ論が好きなら、Schürmann、Klaus-Bernd、Suffix arrays in theory and practice を見てください。

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

そして、何か面白いものを作ったら、私は興味があります

デール・ガーデマン

于 2011-02-15T16:25:58.833 に答える