タグ

Suffix Arrayに関するPnnc205jのブックマーク (1)

  • 無題ドキュメント

    次に、各Suffixにおける大小関係を定義します。この大小関係は辞書式順序です。辞書式順序とは、辞書に並んでいる通りの順番であり、簡単に言えば、 (1)両Suffixを頭(左)から順番に一文字ずつ比較していき、初めて違うところで、文字の大小関係で比較を行う (2)もし、二つを比較していき、片方のSuffixが終わりに達してしまったら、そちらの方が小さいと定義する。 例えば、(1)は上の例でいえば、 S5 と S7を比較するとすると S5 adabra S7 abra 一文字目は両方ともaで、同じなので二文字目(赤い部分)を比較すると、dとbであり、文字の大小関係で d > b なので S7 < S5 という大小関係がつきます。 (2)については、S0 と S7を比較すると S0 abracadabra S7 abra で、頭から4文字は同じであり、S7はデータの最後に達しました。この

  • 1