pixiv insideは移転しました！ ≫ https://inside.pixiv.blog/

回文に親しもう

こちらは ピクシブ株式会社 Advent Calendar 2014 の12月22日の記事です。

こんにちは、おはようございます、こんばんは、エンジニアのneo-nanikakaです。 他のエンジニアの皆さんが、Webサービスやってる会社っぽいエントリーを書いていますが、空気を読まずにWebっぽくないエントリーを書きます。趣味なんだから、仕方ないね。でもこういうのが許されるのは大変良い社風だと思います（唐突なヨイショ）。

回文について

　もしかしたら、回文（かいぶん）という言葉を聞いても何のことやらと思う方もいるかもしれません。回文とは、「しんぶんし」「私、負けましたわ」のように、上から読んでも下から読んでも意味が通る言葉や文を使った言葉遊びです。「山本山」も漢字のままなら回文です。西尾維新さんも「NISIO ISIN」とローマ字表記すれば回文です。

　回文の言葉遊びは日本語に限った話ではなく、外国でも親しまれています。例えば、世界最長の回文単語「saippuakivikauppias」（フィンランド）がギネスブックに登録されています。文章でなら、「Madam, I'm Adam.」「Eva, can I stab bats in a cave?」等があります。

　 本エントリーでは、英小文字による回文（Palindrome）のアルゴリズムを扱います。

その他の言葉遊び

　日本語ではありえないですが、外国語だと逆から読んだ場合に異なる意味になることがあります（「stressed」⇔「desserts」等）。こういう性質を持つものを、シモードニラップ(Semordnilap)と呼びます。Semordnilapもシモードニラップです。また、こういう性質に名前が付いているかは知らないのですが、「iPod!」は紙を逆さまにしても読める点対称な文章です。

回文判定をしよう

長さNの文字列の回文条件は単純です。「最初の文字と最後の文字が等しい」「最初から2文字目と最後から2文字目が等しい」・・・「最初からN/2文字目と最後からN/2文字目が等しい」を全て満たせばそれは回文です

回文判定アルゴリズム O(N)

入力: 長さNの文字列S

出力: 判定結果 true or false

※簡単のために、入力値は英小文字のみで構成されているものとします

    /**
    * 回文判定 O(N)
    */
    public boolean isPalindrome(String string) {
        char[] str = string.toCharArray();
        boolean isPalindrome = true;
        int i = 0, j = str.length - 1;
        while(isPalindrome && i <= j) {
            isPalindrome &= str[i] == str[j];
            i++;
            j--;
        }
        return isPalindrome;
    }

INPUT #1 (Madam, I'm Adam. を入力用に変形したもの）

madamimadam

OUTPUT #1

true

INPUT #2

palindrome

OUTPUT #2

false

INPUT #3

https://gist.github.com/neo-nanikaka/344842d02140919250b3

OUTPUT #3

true

回文判定できた！超簡単！ 完！

で終わるのは相当アレなので、もうちょっとだけ続くんじゃ。

最長回文を見つけよう

さっきの問題は渡された文字列が回文か否かを判定する問題でした。今度は、渡された長さNの文字列に含まれる部分文字列(Substring)の中で最長の回文を求めることを考えましょう。これはLongest Palindromic Substringと呼ばれる問題です(字面が似ているLongest Palindromic Subsequencesという別問題もあります)。例えば「bananas」には"b", "a", "n", "s", "ana", "anana"という6種類の回文が含まれますが、最長はananaなので、これが答えとなります。最長な回文が複数あった場合は全てを求めなければいけません。

この問題はどう解けば良いでしょうか？

素朴な最長回文アルゴリズム O(N3)

誰しもが真っ先に思い付くのが、全ての部分文字列を求めて回文判定を行うアルゴリズムでしょう。コンピュータは繰り返し処理が三度の飯より好きなので、全部試させればよいのです。部分文字列の全列挙にO(N2)、その全てに回文判定を施すので、全体でO(N3)の計算量となります。

LONGEST_PALINDROMIC_SUBSTRING_SLOW 

   /**
    * 最長回文アルゴリズム O(N^3)
    * @param string
    * @return
    */
    public Set<String> longestPalindrome(String string) {
        Set<String> palindromes = new HashSet<String>();
        int N = string.length();
        int longestLength = 0;
        for(int i=0;i<N;i++)for(int j=i+1;j<=N;j++){
            String substring = string.substring(i, j);
            if (isPalindrome(substring)) {
                palindromes.add(substring);
                longestLength = Math.max(longestLength, substring.length());
            }
        }
        Set<String> results = new HashSet<String>();
        for (String palindrome: palindromes){
            if (palindrome.length() == longestLength) results.add(palindrome);
        }
        return results;
    }

INPUT #4

bananas

OUTPUT #4

anana

INPUT #5

abracadabra

OUTPUT #5

ada
aca

INPUT #6

https://gist.github.com/neo-nanikaka/28e53f1057901fe784ef

OUTPUT #6

aabbbaabaaaaaaaaabaabbbaa

このアルゴリズムは、全ての部分文字列を回文判定するので遅いです。#6の5000文字の入力を与えると、筆者の環境で答えが返るまでに5秒以上かかります。

回文の中心を利用する最長回文アルゴリズム O(N2)

ここで、回文の構造の性質に注目してみます。長さが2以上の回文から、先頭と末尾の文字を除去すると、残った文字列は必ず回文になります。これを繰り返すと、長さが1になるか空になります。1になった場合、元の回文は、その文字を中心にする奇数長の回文。空になった場合、元の回文は、ダミーの空文字を中心にした偶数長の回文であったことになります。

例: (abcba) -> (bcb) -> (c)
例: (abccba) -> (bccb) -> (cc) -> ( )

つまり、ある1文字かダミー文字を中心と決めてしまえば、それを中心に持つ回文を全て列挙できます。中心に取る文字を全種類試せば、入力文字列が持つ全ての回文を列挙できたことになり、答えを求めることができます。中心になる文字の候補は2N-1個なのでO(N)。それを中心に持つ回文の全列挙にはO(N)かかるので、全体でO(N2)の計算量で済みます。

LONGEST_PALINDROMIC_SUBSTRING 

   /**
    * 最長回文アルゴリズム O(N^2)
    * @param input
    * @return
    */
    public Set<String> longestPalindrome(String input) {
        char[] string = input.toCharArray();
        int N = string.length;
        Set<Integer> headIndex = new HashSet<Integer>();
        int longestLength = 0;
        for(int center = 0; center < 2 * N + 1; center++) {
            int left, right;
            if (center % 2 == 0) {
                left = center/2 - 1;
                right = center/2;
            } else {
                left = right = center/2;
            }
            while (true) {
                if (!(0 <= left && left < N && 0 <= right && right < N) || string[left] != string[right]) {
                    left++;
                    right--;
                    break;
                }
                left--;
                right++;
            }
            int length = right - left + 1;
            if (longestLength < length) {
                headIndex.clear();
                headIndex.add(left);
                longestLength = length;
            } else if (longestLength == length) {
                headIndex.add(left);
            }
        }
        Set<String> results = new HashSet<String>();
        for (int i: headIndex) {
            results.add(input.substring(i, i+longestLength));
        }
        return results;
    }

これを利用するとINPUT #6は一瞬で答えを返すようになります。やったああああああああああああああんんんん。

ですが、世の中には筆者のように意地悪な入力値を考える奴がいます。

MALICIOUS INPUT

https://gist.github.com/neo-nanikaka/1016009cdcf5b35dfbbe

aのみからなる長さ100,000の文字列です。全ての部分文字列が回文という恐ろしい入力なので最悪計算時間がかかります。ひえー恐ろしい。これを入力に与えると、LONGEST_PALINDROMIC_SUBSTRINGは筆者の環境で3秒かかります。LONGEST_PALINDROMIC_SUBSTRING_SLOWに至っては計算の冒険に出て一生帰ってこないでしょう。え？入力がでかすぎるだけだろふざけんなって？確かに、文字列長を大きくすれば当然計算量はかかるのですが、この10万文字の入力を与えても一瞬で答えを返す賢いアルゴリズムが存在します。

Manacher O(N)

簡単のために奇数長の回文のみを扱います。偶数に関しても、ダミー文字を使えば同じ議論ができます。 Manacherは、文字列中の各位置 i を中心にしたときの回文の長さを配列に持ち、この配列を左から右へ順番に埋めていこうとするアルゴリズムです。その際、LONGEST_PALINDROMIC_SUBSTRINGのように、毎位置で最長回文を求めるのではなく、実行の過程で計算してきた値を使って無駄な計算を行わないように設計されたアルゴリズムになっています。Wikiだと最長回文を求める位置を(interesting position)と呼んでいます。Manacherはこの、interesting positionの回数が必要最低限に押さえられていると考えられます。

回数削減のために次の補題を利用します

文字列 S のある位置 i を中心とする最長回文を s とする。
s のlongest palindromic proper suffixを t とすると
i から t の中心までにある文字はsより長い回文の中心にならない

証明に背理法を使います。

t を s のpalindromic proper suffixとし、s の中心より右で、t の中心より左にある文字を中心に持ち、|s| <= |u|であるような回文 u があると仮定します。

u の最右端の文字は s の最右端よりも右側にあります。u は s の中心より右に中心を持ち、s と同じかそれ以上長いからです。

次に、u の最右端が s の最右端と一致するまで u から両端の文字を削って u' とします。これで |u'| < |s| となります。u' は s より右側に中心を持ち、右端が同じだからです。

さて、ここで u' は s のpalindromic proper suffixになっています。しかし、|t| < |u'|です。u' は t より左側に中心を持ち右端が同じだからです。

これは、t が s のpalindromic proper suffixであることと矛盾してしまうので、仮定した u は存在しないことになります。

※longest palindromic proper suffix を実を言うと正しく筆者が解釈できているか分かりません(えっ)。筆者は、回文の右半分に中心を持ち、文字列の右端と回文の右端を共有するような最長の回文だと捉えて、Wikiを読み進めました。 例えば、 abaccdccaba の場合、longest palindromic proper suffix は aba だと解釈してます。

この補題は、位置 i の最長回文 s を見つけたときに、s の右端にある長そうな回文だけが、s を超える長さを持つ回文になり得ると言っています。

これに加えて、次のような観察ができます。

最長回文sがあったとします。

その中心から順番に左のインデックス i を考えます。これらは既に最長回文が求まっています。

もし、位置iの最長回文uの1文字目が、sの1文字目より真に右側にあったなら、sの反対側の位置 j の最長回文もuになっているので、即座に位置 j の最長回文が求まることになります。

あるところで、 u の1文字目が条件を満たさなくなるはずです。そのときの i の反対側の位置 j が次のinteresting positionになります。

この、計算しなくても最長回文の長さが求まる条件を数式にしたのがありがたいことにネットで公開されています。 rad[i]は位置 i　の最長回文sの長さの半径です。

任意の 0 <= i < N について
rad[i-k] < rad[i] - k ならば rad[i-k] = rad[i+k]

さっき観察した条件が rad[i-k] < rad[i] - k で、対称性を利用して計算することなく最長回文の長さが求まっている様が rad[i-k] = rad[i+k] です。

まとめると、次のような擬似アルゴリズムになります

MANACHER 

1. 入力文字列Sにダミー文字を挟んでおく。
2. rad[] を用意して0で初期化する。
3. Sの最初の文字を interesting position とする
4. interesting position の最長回文を素直に求めて、rad[] に入れる
5. i をinteresting position として、kを1ずつ増やす
   if |S| < i + k
      then 超えるならば終了
   elseif rad[i-k] < rad[i] - k
      then rad[i+k] = rad[i-k] して、5へ
   else 
　　  次のinteresting position を i+kにする
      rad[i+k]は、rad[i] - kと同じかそれ以上の長さになるので、そこは調べずにステップ4を実行する

javaだとこうなります

   public Set<String> manacher(String string) {
        StringBuilder sb = new StringBuilder();
        sb.append("#");
        for (char c: string.toCharArray())sb.append(c+"#"); //ダミー文字を突っ込む
        char[] s = sb.toString().toCharArray();
        int N = s.length;
        int max = 0;
        
        int[] rad = new int[N];
        for (int i=0, j=0; i<N;) {
            while(0 <= i-j && i+j < N && s[i-j]==s[i+j]) j++; //rad[i]を素直に求める
            rad[i] = j;
            max = Math.max(max, j); // 最大値は記憶しておく
            // 計算しなくても求められる部分を走査
            int k;
            for (k=1; 0 <= i-k && i+k < N && rad[i-k] < rad[i]-k; k++) {
                rad[i+k] = rad[i-k];
            }
            i+=k; // 次のinteresting position
            j = Math.max(j-k, 0); // interesting position は rad[i]-kと同じか長い回文を持つので考慮させる
        }
        Set<String> results = new HashSet<String>();
        String subs = new String(s);
        for(int i=0;i<N;i++){
            if (rad[i] == max) {
                String sub = subs.substring(i-max+1, i+max);
                results.add(sub.replaceAll("#", ""));
            }
        }
        return results;
    }

MALICIOUS INPUTに対して 100ms 程度で答えられるようになりました。

本当はこれがO(N)になっているかを示さなくてはいけないんですが、それはWikiに任せることにします

まとめ

回文と、回文にまつわるアルゴリズムを紹介しました。とてもシンプルな最長回文から、回文の性質を突いた最長回文、より深い観察から生み出されたManacherのアルゴリズムまでをカバーしました。5000文字でいっぱいいっぱいだった状態から、10万文字程度までを扱える状態になったので、アルゴリズムの力はすごいなぁと思ってくれる方がいれば幸いです。Manacherの解説は若干日本語が怪しいし、細かいところで何か間違っているかもしれませんが、根本の流れは正しいはずなのでノリを感じてくだされば十分です。 ところで、回文を扱うときはManacherが絶対いいよと言いたいわけではありません。効率のよいアルゴリズムは往々にしてコードが複雑です。ちょっとした用途で最長回文を見つけたいのであれば、シンプルな最長回文アルゴリズムで十分です。状況に応じて、アルゴリズムを使い分ければいいと思います。

エンジニア募集！

ピクシブではWebアプリケーションエンジニアを絶賛募集中です。アルバイトも積極的に募集しています。

Next is...

明日は、@i315が若さ溢れるフレッシュな記事を書いてくれることでしょう。

References

http://www.wcipeg.com/wiki/Longest_palindromic_substring

http://www.prefield.com/algorithm/string/manacher.html

http://spinda2.blog48.fc2.com/blog-entry-465.html