アルゴリズム投棄場

[udemegane]

　 ∧,,∧
　( `･ω･) ようこそアルゴリズム投棄スレへ！
　/　∽ |
　しー-Ｊ
ここは閃いたアルゴリズムを投下して考察する、
硬派なトレーニングスレです。

さあ、存分に腹筋するがよい↓(｀･ω･´)

[udemegane]

案１

出発点：
・文字列の断片s_iの組み方によっては、編集距離が虫食い状態からほとんど変化しない可能性がある
・というかxを全部aにするだけで編集距離を40%も落とせる(len(T)が40万、そのうち2/5がxだから虫食いデータとの編集距離は16万程度、文字aの出現確率は40%だからxを全部aにすると16×0.6で96000くらいになる　当たり前だけど実際に計算してもそうなった)

必要なもの：
・あいまい検索ができるアルゴリズムとデータ構造　複数マッチングに強いとなおよし

---

1. とりあえずs_iとT'の部分列に完全に一致する場所があったら埋める。

2. len(s_i)が長い物から順にあいまい検索をかけて場所を特定する。
   例）
   

3. 工程２を繰り返す。当然len(s_i)が短くなればなるほどあいまい検索で場所を特定できる確率は下がる。xをaに置換する作業は編集距離を40%減少させるから、len(s_i)が短くなりすぎてあいまい検索で正確な位置が特定できる確率が40%?(要計算)を下回り始めたら、T'の残りの虫食い箇所は全てaに置換しておしまい。
   何回繰り返すかは糸井氏の素晴らしいデータ元にがんばって計算するかサンプルデータで試しまくってゴリ押しで決める。
   アホコラみたいに木構造使って複数マッチングできるやつを使うなら長いやつから順番にやるというより40パーセント以上の確率で正しい場所がわかる長さn以上のs-iのみをエッジにもつトライ木作ってマッチングして、n未満のs-iは全部切り捨てるとかそんな感じになる？

4. T'出力しておしまい

---

特徴：
・簡単な考え方だから理解しやすい　

欠点：
・誰でも思いつく　多分いまごろ全く同じことを他の人も考えている

擬似コード：
まだ考えてないよ

実装：
暇な時間とやる気が同時に訪れたらやります。これを読んでいる君がやってくれたら神

蛇足:マルチスレッド化させたらスレッドが指数的に増えるから速そう　でも同期が絶対超めんどくさい

とりあえず明日あたり工程2を何回繰り返すのがベストなのか計算してみます。

[pysan3]

読んだ感じ、一回xをすべてaに置換してから一番近いsを当てはめていくアイディアは良きだと思う
長いsから順に(or len(s_i) > nなものを任意順で)やる感じで多分ある程度の速さを保ちつつ、最低限の正確性を出せる感じかな？((計算したわけではない

ちなみにテストケースではlen(s_i) <= 2なs=iが全体の2割弱を占めているので、そいつらを省いて計算するだけでもそこそこ早くなる気がする
上のアルゴリズムではそれが可能なのでよいと思う

ただ、言ってる通り、多分(ほかグループと比較して)まーまーな結果になる気がする。

あと絶望的に実装がめんどうww((特に並列処理はだるいんご←一応#include <pthread.h>で意外といけそう？

[udemegane]

去年の1位はマルコフアルゴリズムなるものを使ったらしいです
去年の問題はa,b,c,xの4種だけ　文字列長については聞かないとわからないです

[pysan3]

去年の1位はマルコフアルゴリズムなるものを使ったらしいです
去年の問題はa,b,c,xの4種だけ　文字列長については聞かないとわからないです

その情報はありがたい
マルコフアルゴリズム(?)勉強します...

[pysan3]

アホコラ

s = {"ab", "abc"};
t = "abcabcabcab";

とすると、出力は以下のようになる。

なんかいい方法思いつきませんか？

[siro53]

良い方法とは？(それで合ってるのでは？)

[pysan3]

これを用いた、いい問題の解き方

[siro53]

• まずSの要素の中で完全に一致する部分があったらそれを埋める。
• 残ったSの要素であいまい検索を掛けたい。なので次のようにする。
  　1. Sの要素のそれぞれについて、prefixが一致してる部分文字列を全て列挙する
  　2. その中で一致するものがあればそれを当てはめる
• これを条件を満たすまで繰り返す。
• 条件を満たしたことが分かった後、置換した後残っているxを、a,b,c,dの割合がデータ分析したものに近づくように埋めていく。

...とか？（あいまい検索の部分がかなり難しそう...）

アホコラは辞書の中の単語が完全に一致している部分の検索なら簡単だけど、部分的に一致しているのを探すのって難しそう（なのでprefix(先頭)が一致してたら...みたいに妥協するみたいな）

[pysan3]

報告
アホコラのあいまい検索を実装しました(pysan_testsブランチ)
現在の性能は9 < len(s_i) <= 20の範囲のsをキーとして所要時間114.42s
計算時間は最大のlen(s_i)の指数関数で長くなっていきます O(n+2^m), n := len(t), m := max(len(s_i))
計算空間は比例(なので余裕)　O(m), m := sum(len(s_i))

編集距離はまだ計算してない(というか出力すら実装してない)けど理論上(ある程度sが長い場合)ほぼ正確だと思われる。
正確性は、多分指数比例してよくなるはず？

もっと速い方法を誰か教えて...指数時間は遅い(´;ω;｀)

[udemegane]

大変遅くなりました
ボイヤームーアを実装しました。
現状色々無駄が多いので改良できるとこが無限にあります（いつかやります）
あいまい検索対応のためオリジナルと微妙に動作が違うのでlineの添付ファイルかudemeganeブランチのりどみを読んでください
ぱっと見でどんな動きしてるか一発でわかるようにしておいたので"もっといいアルゴリズムあるぜ！！"って方はぜひ改良してください
ただそのせいでりどみめちゃくちゃ長いのでvscodeなりでPC閲覧推奨します　スマホとメモ長はめちゃくちゃ見づらいです
あと入出力関連が死んでます　誰か助けてください

[udemegane]

追記：大嘘です１０秒より全然早いです
またs_iは不一致の場合平均して4.3ほど右にずれます

[udemegane]

[udemegane]

すみませんなんか色々勘違いしてました

長さ100~19を7秒で探索できます。精度は83.5%です

[udemegane]

火曜日時点で考えていたアルゴリズムによる高速化に失敗しました....
別の手法を考えます

[udemegane]

なんか色々おかしかったので調べてみたところ既に文字列長22あたりで重複が発生しています
単純にtを端から見ていって最初に当てはまったところにs_iを割り当てていくと文字列長20までで大体1万5000文字、文字列長10までで7万文字の割り当てミスが発生します
よくわからんsegmentation faultの原因とか高速化し損ねた原因はこいつでした
どうすればいいでしょう

[udemegane]

解決策が思いつかなかったのでとりあえず高速化しました。

100~20を1.3秒で探索できます。
マルチスレッド化しました。プロセッサのスレッド数までは高速になります。
以下の画像の通り、マルチスレッド処理ができていることが分かります。CPU のスレッド数以上のスレッドを作成しても意味はないです。
シモセらさんの6800kは6c/12tなのでThreadNumは１２に設定します。

追記：printfのせいで速度が半分になってたので消しました

[udemegane]

家ので12スレッド動作させたら1秒切ったやったー
でもなぜかdat1だけ無限ループ？に突入する... なんでだろう

[pysan3]

家ので12スレッド動作させたら1秒切ったやったー

1秒切ったのはすげえ

[udemegane]

ただコンパイルオプションに-pthreadが必要になるから白の言ってたコンパイルオプションの書き換えが必須になる
やり方教えてください....