接尾辞配列
ぬお。日本語版 Wikipedia に Suffix Array の項目が。接尾辞配列なんていっている人いるのか、とか思ったけど検索したらそこそこ使われているし。
で、どうも英語版の翻訳らしんだけど、日本語訳がすごいことになっているね。
The easiest way to construct a suffix array is to use an efficient comparison sort algorithm. This requires O(nlogn) suffix comparisons, but a suffix comparison requires O(n) time, so the overall runtime of this approach is O(n2logn).
接尾辞配列を構築する最も容易な方法は、効率的な比較ソートアルゴリズムを利用することである。接尾辞は O(nlogn)回の比較が必要とされるが、比較ソートアルゴリズムによっては、接尾辞の比較は O(n)回となる。従って全体的な比較回数は O(n2logn)回となる。
もう、訳がどうのこうのいう前に日本語としても意味が分からないし。比較は O(n) 回なのかそれとも O(n log n) 回なのか、それとも O(n^2 log n) 回なのかと。いろいろ無理矢理補完しすぎてもう無茶苦茶。
「O(n) time」 は 「O(n) 回」じゃなくて「O(n) 時間」。回数なら times にならないとおかしい。正しくは「O(n log n)回の比較が必要とされるが、接尾辞の比較は O(n) の時間がかかるので、全体的な実行時間は O(n^2 log n) となる」。
もういっちょ。
To avoid redoing comparisons, extra data structures giving information about the longest common prefixes (LCPs) of suffixes are constructed, giving O(m + logn) search time.
比較をやり直すことの無いように、最も長い文字列である「接頭辞」(LCP)に関する情報を与える余分なデータ構造は、O(m + logn)回の検索をかけて構築される。
おい。これじゃまるで「接尾辞」=「LCP」じゃねーか。そしてやっぱり日本語がおかしい。LCP つうのは Longest Common Prefix のことで、接尾辞間の最長共通接頭辞(の長さ)のこと。LCP の構築には検索は必要ないし、O(n) で計算できる。正しくは「接尾辞間の最長共通接頭辞を計算しておけば、比較のやり直しを避けることができ O(m + log n)の計算時間で済む」だろう。ちなみにこれには Range Minimum Query*1 というのを併用する。
つうか、Applications の前半省略されまくりだな。なぜ、一番重要な部分を省く。
と、こんなことを書いている暇があったら、お前が直せと突っ込まれそうなので(というか自分なら突っ込む)、とりあえず Wikipedia のアカウントを作っておいた。あとで直す。
追記
編集はじめたけど、これもすごいな。
元の文字列が利用可能な場合、それぞれの接尾辞が0起点の添字を付与されたか、それとも1起点によるものかは容易に判断できる。
原文はこれ。
If the original string is available, each suffix can be completely specified by the zero-based or one-based index of its first character.
あはは。
