最長の共通部分

質問

はじめて質問させていただきます。

二つのデータの最大長の共通部分を求めるための、
なるだけ高速なアルゴリズムを探しています。

たとえば、
データ1:『EFGABCDEFGABCDEFGHAABCDEFG』
データ2:『EFGHABCDEFGABCDEFGAABCDEFG』
ですと

データ1の4バイト目のAから始まる14バイトと
データ2の5バイト目のAから始まる14バイトが一致。
が求めたい答えです。

細かい条件をならべると、

1) 文字列ではなくバイナリデータである。
2) データサイズは、最大で数MB程度を想定。
3) 同じ並びの繰り返しなどを多く含んでいる可能性を否定できない。
4) 連続した１つのバイト列で最長なものが知りたい。
5) まれに最長ではなく、最長から二番目が出力されてしまう程度の、
誤差はあってもよい。
6) 一定長(例えば全体の10%)以下の共通部分であれば、無視してもよい。

といった感じなのですが。

ソートを使う、ハッシュを使う、飛び飛びに探索する等、
いろいろアルゴリズムを考えてみましたが、どれもパッとしません。

先ほどグーグルで検索していて、どうやらかなり難しいらしい
ということに気づきました。

なにか、ご存知の方いらっしゃいましたら、
アドバイスをお願いいたします。

回答No.3

graphaffine · ベストアンサー

あまり良く考えてませんが、Ｔｒｅｉ構造だともしかするといけるかも知れない。

Ｔｒｅｉ構造は木構造をベースにしてますが、
長男次弟構造を使うと数千万ノードの木が実現できます。

お礼

＞あまり良く考えてませんが、
＞Ｔｒｉｅ構造だともしかするといけるかも知れない。

回答ありがとうございます。
アルゴリズムの本を読んだときに、
トライ構造はなんとなく難しそうなので読まなかったのを、
思い出しました。
これはよいかもしれません。
調べていくうちに、自分で考えたアルゴリズムが、
サフィックスアレイとかいうのと近そうなので、
それに気持ちが傾いているのですが、
文字列比較の計算量がばかにならなくてどうしたものかと迷っています。
正確なことはわかりませんが、トライ構造をうまく改造できれば、
ソートの計算量をさげられるかもしれません。
よい情報をありがとうございました。

回答No.5

sha-girl

#1です。
表のサイズに関しては対角線以外の領域をある程度無視すれば
かなりメモリを節約できると思います。
ご指摘の通り
データ1:『ABCDF/ABCEFG』
データ2:『ABCEFG/ABCDF』
なら最長一致は
「/ABC」という事になる可能性があります。
その代わり計算量は少なく非常に高速です。

勿論DPマッチングを応用して一致項目が多い順に何パターンか保存し
「ABCEFG」同士が一致してるという事を導く事も可能だと思います。
その辺は精度と速度のトレードオフになると思います。

お礼

再度の回答ありがとうございます。

＞表のサイズに関しては対角線以外の領域をある程度無視すれば
＞かなりメモリを節約できると思います。

よく考えてみましたが、少ししかずれたらダメということですから、今度は、

データ1:『ABCDF121212』
データ2:『789123ABCDF』

の『12』にヒットするはずで、これはこれでダメなのではないでしょうか。

＞データ1:『ABCDF/ABCEFG』
＞データ2:『ABCEFG/ABCDF』
＞勿論DPマッチングを応用して一致項目が多い順に何パターンか保存し
＞「ABCEFG」同士が一致してるという事を導く事も可能だと思います。

これも考えて見ましたが、
こういう２ブロックが入れ替わっているだけの
単純なデータならばよいのですが、
現実には、もっと多くのブロックで構成されているデータが、
並べ変わっているといると、まったく関係のないところにヒットしそうで、
怖いです…。

私の実力がないのが一番の問題かもしれませんねorz。

というわけで、今回は迷った末、DPマッチングを使わずに
自作の適当なアルゴリズムで行くことにしましたが、
面白いアルゴリズムを教えていただいて、ありがとうございます。
大変、勉強になりました。

回答No.4

graphaffine

#3のものです。
間違えた。Ｔｒｅｉ構造ではなく、Ｔｒｉｅ構造です。
ちなみに、読み（トライです）に引きずられて間違ってしまった。

回答No.2

neKo_deux

> 5) まれに最長ではなく、最長から二番目が出力されてしまう程度の、誤差はあってもよい。
> 6) 一定長(例えば全体の10%)以下の共通部分であれば、無視してもよい。
> いろいろアルゴリズムを考えてみましたが、どれもパッとしません。

の条件ですと「遺伝的アルゴリズム(GA)」がそこそこ良い結果を出せるのでは？と思います。
MSのサイトが分かりやすいです。

アルゴリズム入門 : 第 5 章 知識情報処理入門
http://www.microsoft.com/japan/msdn/academic/Articles/Algorithm/05/

--
ただ、難しいのは評価式、符号化の選択方法ですね。
No.1さんの参考URLの末尾にもある、

| いずれにせよ、HMMのモデルの格好を定めることは、深遠で時として悩ましい問題です。

のような問題はついて回ります。

参考URL：

http://www.microsoft.com/japan/msdn/academic/Articles/Algorithm/05/

お礼

遺伝的アルゴリズムですか。
まったく思い浮かびませんでした。
そういう使い方があるのですね。
探索にかける時間に制限がある場合は良さそうですし、
データが巨大な場合はこれが一番いいかもしれません。

＞ただ、難しいのは評価式、符号化の選択方法ですね。
＞No.1さんの参考URLの末尾にもある、

難しいですね。
やってみたいですが、私にできるでしょうか。

回答ありがとうございました。

回答No.1

sha-girl

「DPマッチング」で検索してみてください。

http://staff.aist.go.jp/toru-nakata/dpmatching.html

お礼

回答ありがとうございます。

せっかく教えていただいた、DPマッチングですが、
どうやったら今回のケースに、このアルゴリズムが使えるのか、
私にはどうも理解できませんでした。
もう少し質問させてください。

参照サイトの説明文を読む限り、得られるのは、
不連続のバイト列なんですよね？？。

4) 連続した１つのバイト列で最長なものが知りたい。

なので、そこから連続したバイト列を得ないと
いけないのですが、うまい方法が見つかりません。
DPマッチングですと、たとえば、

データ1:『ABCDF/ABCEFG』
データ2:『ABCEFG/ABCDF』

なら

データ1の1バイト目から始まる飛び飛びの『ABCF/ABCF』と
データ2の1バイト目から始まる飛び飛びの『ABCF/ABCF』が一致

と得られるのでしょうけれど、そこから正しい答え

データ1の7バイト目から始まる『ABCEFG』と
データ2の1バイト目から始まる『ABCEFG』が一致

を導くのが困難です。
実際もっと複雑なデータですし、
あちらこちらでデータが入れ替わっていたりすると、
どんどん得られるデータと欲しいデータが
無関係になっていくのではないでしょうか。
と疑問に思うのですがどうでしょうか。

それから、

2) データサイズは、最大で数MB程度を想定。

なので、たとえばデータが3MBで、
コストを表すのにINT形を用いたとすると、

表のサイズが、

3M×3M×4B＝36TB

と巨大になってしまって、メモリーはおろか、
ハードディスクにも入りません。
といって、何度も表をつくり直していては遅くなってしまいますし、
どうしたらよいのでしょうか？。