はじめて質問させていただきます。
二つのデータの最大長の共通部分を求めるための、
なるだけ高速なアルゴリズムを探しています。
たとえば、
データ1:『EFGABCDEFGABCDEFGHAABCDEFG』
データ2:『EFGHABCDEFGABCDEFGAABCDEFG』
ですと
データ1の4バイト目のAから始まる14バイトと
データ2の5バイト目のAから始まる14バイトが一致。
が求めたい答えです。
細かい条件をならべると、
1) 文字列ではなくバイナリデータである。
2) データサイズは、最大で数MB程度を想定。
3) 同じ並びの繰り返しなどを多く含んでいる可能性を否定できない。
4) 連続した1つのバイト列で最長なものが知りたい。
5) まれに最長ではなく、最長から二番目が出力されてしまう程度の、
誤差はあってもよい。
6) 一定長(例えば全体の10%)以下の共通部分であれば、無視してもよい。
といった感じなのですが。
ソートを使う、ハッシュを使う、飛び飛びに探索する等、
いろいろアルゴリズムを考えてみましたが、どれもパッとしません。
先ほどグーグルで検索していて、どうやらかなり難しいらしい
ということに気づきました。
なにか、ご存知の方いらっしゃいましたら、
アドバイスをお願いいたします。
No.3ベストアンサー
- 回答日時:
あまり良く考えてませんが、Trei構造だともしかするといけるかも知れない。
Trei構造は木構造をベースにしてますが、
長男次弟構造を使うと数千万ノードの木が実現できます。
>あまり良く考えてませんが、
>Trie構造だともしかするといけるかも知れない。
回答ありがとうございます。
アルゴリズムの本を読んだときに、
トライ構造はなんとなく難しそうなので読まなかったのを、
思い出しました。
これはよいかもしれません。
調べていくうちに、自分で考えたアルゴリズムが、
サフィックスアレイとかいうのと近そうなので、
それに気持ちが傾いているのですが、
文字列比較の計算量がばかにならなくてどうしたものかと迷っています。
正確なことはわかりませんが、トライ構造をうまく改造できれば、
ソートの計算量をさげられるかもしれません。
よい情報をありがとうございました。
No.5
- 回答日時:
#1です。
表のサイズに関しては対角線以外の領域をある程度無視すれば
かなりメモリを節約できると思います。
ご指摘の通り
データ1:『ABCDF/ABCEFG』
データ2:『ABCEFG/ABCDF』
なら最長一致は
「/ABC」という事になる可能性があります。
その代わり計算量は少なく非常に高速です。
勿論DPマッチングを応用して一致項目が多い順に何パターンか保存し
「ABCEFG」同士が一致してるという事を導く事も可能だと思います。
その辺は精度と速度のトレードオフになると思います。
再度の回答ありがとうございます。
>表のサイズに関しては対角線以外の領域をある程度無視すれば
>かなりメモリを節約できると思います。
よく考えてみましたが、少ししかずれたらダメということですから、今度は、
データ1:『ABCDF121212』
データ2:『789123ABCDF』
の『12』にヒットするはずで、これはこれでダメなのではないでしょうか。
>データ1:『ABCDF/ABCEFG』
>データ2:『ABCEFG/ABCDF』
>勿論DPマッチングを応用して一致項目が多い順に何パターンか保存し
>「ABCEFG」同士が一致してるという事を導く事も可能だと思います。
これも考えて見ましたが、
こういう2ブロックが入れ替わっているだけの
単純なデータならばよいのですが、
現実には、もっと多くのブロックで構成されているデータが、
並べ変わっているといると、まったく関係のないところにヒットしそうで、
怖いです…。
私の実力がないのが一番の問題かもしれませんねorz。
というわけで、今回は迷った末、DPマッチングを使わずに
自作の適当なアルゴリズムで行くことにしましたが、
面白いアルゴリズムを教えていただいて、ありがとうございます。
大変、勉強になりました。
No.2
- 回答日時:
> 5) まれに最長ではなく、最長から二番目が出力されてしまう程度の、誤差はあってもよい。
> 6) 一定長(例えば全体の10%)以下の共通部分であれば、無視してもよい。
> いろいろアルゴリズムを考えてみましたが、どれもパッとしません。
の条件ですと「遺伝的アルゴリズム(GA)」がそこそこ良い結果を出せるのでは?と思います。
MSのサイトが分かりやすいです。
アルゴリズム入門 : 第 5 章 知識情報処理入門
http://www.microsoft.com/japan/msdn/academic/Art …
--
ただ、難しいのは評価式、符号化の選択方法ですね。
No.1さんの参考URLの末尾にもある、
| いずれにせよ、HMMのモデルの格好を定めることは、深遠で時として悩ましい問題です。
のような問題はついて回ります。
参考URL:http://www.microsoft.com/japan/msdn/academic/Art …
遺伝的アルゴリズムですか。
まったく思い浮かびませんでした。
そういう使い方があるのですね。
探索にかける時間に制限がある場合は良さそうですし、
データが巨大な場合はこれが一番いいかもしれません。
>ただ、難しいのは評価式、符号化の選択方法ですね。
>No.1さんの参考URLの末尾にもある、
難しいですね。
やってみたいですが、私にできるでしょうか。
回答ありがとうございました。
No.1
- 回答日時:
回答ありがとうございます。
せっかく教えていただいた、DPマッチングですが、
どうやったら今回のケースに、このアルゴリズムが使えるのか、
私にはどうも理解できませんでした。
もう少し質問させてください。
参照サイトの説明文を読む限り、得られるのは、
不連続のバイト列なんですよね??。
4) 連続した1つのバイト列で最長なものが知りたい。
なので、そこから連続したバイト列を得ないと
いけないのですが、うまい方法が見つかりません。
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
と巨大になってしまって、メモリーはおろか、
ハードディスクにも入りません。
といって、何度も表をつくり直していては遅くなってしまいますし、
どうしたらよいのでしょうか?。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- 数学 特定の座標点を通る回帰を行う方法について。 2 2022/10/10 10:27
- Excel(エクセル) 結合セルのソートについて 5 2022/04/22 11:57
- Visual Basic(VBA) 【VBA】データを入力後に,同一シート内に履歴として転記するVBAコードを教えていただきたいです。 3 2022/11/16 01:37
- スーパー・コンビニ 最近バイトを始めた高校生です。 スーパーでバイトしているのですが、 こないだバイトした後日に店長に 3 2023/01/30 09:41
- Excel(エクセル) 関数EXACT(文字列,文字列)とexcelVBA 3 2022/04/14 15:07
- C言語・C++・C# [C言語] コメント文字列を無視して、数値データを読み込むプログラム部分について 5 2022/10/05 11:03
- その他(プログラミング・Web制作) プログラミング python pandas 固定長データの出力 2 2022/08/16 11:22
- Y!mobile(ワイモバイル) Ymobile!データ増量オプション(550円)1年無料経過後 解約・契約繰り返して使えますか? 5 2023/05/11 09:11
- 仕事術・業務効率化 ライティングに興味が出たのでPCスキルをつけたい 4 2022/08/31 22:15
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正しい五十音順について
-
[ EXCEL VBA ] 図形を読み込む...
-
画像から文字を認識してテキス...
-
アルゴリズムとプロトコールの違い
-
期間重複チェックがわかりません
-
BCDについて
-
ハッシュアルゴリズム
-
あいまい検索(文字列一致率)
-
検索エンジンペナルティについて
-
シードを考慮したトーナメント...
-
JPEG圧縮で8×8に分割する理由に...
-
偏りのある乱数のアルゴリズム
-
2点間の距離の最大値を求めたい
-
Visual studio2019 C#で生まれ...
-
2つのテキストファイルを比較...
-
乗換案内の作り方が知りたいです。
-
Officeのラスタ画像の拡大縮小...
-
C♯で電卓を作成しています。演...
-
アルゴリズムの表現方法
-
トップダウン解析とボトムアッ...
おすすめ情報