たにしきんぐダム

プログラミングやったりアニメやゲーム見たり京都に住んだりしてます

プレーンな Aho-Corasick を実装したけどそんなに早くなかった

TL;DR

  • TypeScript で Aho-Corasick を実装しました https://github.com/tanishiking/aho-corasick-js
  • ベンチマークとってみたところだいたいのケースで普通のTrieで複数パターンマッチするほうが早かった https://github.com/tanishiking/aho-corasick-benchmark
  • (プレーンな) Aho-Corasick は Trie の最悪時間計算量を緩和するものの、実際の検索では failure state への遷移が非常に多く、ループの数は減らせるものの時間がかかってしまう(推測)
  • 状態遷移表(やダブル配列)を使ったより高速な Aho-Corasick の実装や、Boyer-Moore と Aho-Corasick が合体した Commentz-Walter とか、より高速に複数パターンの検索を実装する方法はある

参考


Aho-Corasick on TypeScript

JSで複数の文字列パターンを高速に検索したいことがあり、有名かつ実装が割と簡単という Aho-Corasick を TypeScript で実装してみた(ナイーブに実装されたものはいくつかnpmに公開されているが、しっかりメンテされていて安心して使えそうなものはなかった)。

github.com www.npmjs.com

(実装してみたと言っても GitHub - robert-bor/aho-corasick: Java implementation of the Aho-Corasick algorithm for efficient string matching による良く出来た Java 実装を部分的に TypeScript に移植しただけなのだが...)


ベンチマーク環境


ベンチマーク結果

いくつかのパターンに対してベンチマークをかけてみた。

自然言語っぽい sentence に対するベンチマーク

  • chance.sentence によって生成した sentence が検索対象
    • ちなみにsentenceにより生成されるwordはそれぞれ平均5,6文字だそう。
  • chance.word で生成した単語(?)郡がキーワード

長さ10000単語のsentenceに対して 10000キーワードを検索

❯ node index.js -k sentence --keywords 10000 --length 10000             
indexOf loop x 2.99 ops/sec ±1.81% (12 runs sampled)
simple trie x 111 ops/sec ±2.07% (67 runs sampled)
aho corasick x 33.11 ops/sec ±2.60% (54 runs sampled)

長さ10000単語のsentenceに対して 500000キーワードを検索

❯ node index.js -k sentence --keywords 500000 --length 10000             
indexOf loop x 0.04 ops/sec ±34.98% (5 runs sampled)
simple trie x 25.42 ops/sec ±14.62% (47 runs sampled)
aho corasick x 11.85 ops/sec ±17.90% (27 runs sampled)

長さ10000単語のsentenceに対して 100キーワードを検索

❯ node index.js -k sentence --keywords 100 --length 10000
indexOf loop x 347 ops/sec ±1.53% (82 runs sampled)
simple trie x 224 ops/sec ±1.03% (82 runs sampled)
aho corasick x 94.35 ops/sec ±2.48% (67 runs sampled)
  • キーワード数が少ないと単純な indexOf のループが一番早い(それはそう)
  • Aho-Corasick は総じて Trie に負けてる

機械的な文字列集合(DNA配列とか)(文字種少なめ) に対するベンチマーク

文字種が少なくキーワードが多い場合は Aho-Corasick の failure 遷移が よく効いてくるのではないかと思い、Aho-Corasick に有利な条件のベンチマークを設定してみた。

長さ1000の文字列に対して、10000キーワードで検索

❯ node index.js -k string --keywords 10000 --length 1000 --pool abcdefg 
indexOf loop x 54.19 ops/sec ±15.41% (45 runs sampled)
simple trie x 2,825 ops/sec ±9.39% (75 runs sampled)
aho corasick x 4,001 ops/sec ±3.11% (74 runs sampled)

長さ10000の文字列に対して、10000キーワードで検索

❯ node index.js -k string --keywords 10000 --length 10000 --pool abcdef
indexOf loop x 6.46 ops/sec ±28.38% (20 runs sampled)
simple trie x 305 ops/sec ±2.82% (72 runs sampled)
aho corasick x 223 ops/sec ±16.66% (62 runs sampled)
  • やはり文字種の少ない環境かつ検索キーワードが多い環境だと failure 遷移が効いてくる(一方で Trie は無駄な遷移が目立ってくる)のか、Aho-Corasick に軍配が上がった
  • しかし検索対象が長くなると Trie に逆転される...

プレーンな Aho-Corasick が Trie よりも遅い理由の推測

Aho and Corasick [AC75] presented a linear-time algorithm for this problem, based on an automata approach. This algorithm serves as the basis for the UNIX tool fgrep. A linear-time algorithm is optimal in the worst case, but as the regular string-searching algorithm by Boyer and Moore [BM77] demonstrated, it is possible to actually skip a large portion of the text while searching, leading to faster than linear algorithms in the average case https://www.researchgate.net/publication/2566530_A_Fast_Algorithm_For_Multi-Pattern_Searching

  • とあるように、Aho-Corasick は Trie による検索の最悪ケース (最長パターンのギリギリまで遷移して、受理状態に到達するギリギリで遷移に失敗するのを繰り返す場合 abcdefg というキーワードを abcdef という文字列から検索するみたいな) の対策にはなっていそうではある。
  • しかし実際の文字列検索では、確かに Trie は検索対象の文書に対して二重ループを走らせる必要があるものの、内側のループ(Trieで構築されたオートマトン上を遷移する過程)ではだいたいの場合、早々に遷移に失敗するはず
    • そのため最悪ケースでは二重ループを繰り返すものの、実際はそんなに時間かからないのではないか。
  • 一方 Aho-Corasick は二重ループを取り除き、一回の検索対象文字列に対する走査ですべての検索キーワードを見つけることができるが、遷移に失敗した場合に(failure遷移先から)遷移に成功するまでfailure遷移を複数回繰り返すことになる。
    • そのため検索対象文字列と、検索するキーワードがよく似ており、遷移が成功しやすい環境では failure 遷移による高速化がよく効くものの、遷移が失敗しやすい環境では(複数の) failure 遷移が多くなり、それによる検索速度の劣化が著しいのではないか。

このような原因でプレーンな Aho-Corasick 実装が Trie 実装に負けたのではないかと考えています(もしかすると単純に僕の実装がミスってて不要な状態遷移とかが起きてるのかもしれないが...何度読みなおしてもそのようなことにはなってないように見える)。

詳しいかたいらっしゃったら教えて下さい or 読むべき本/論文などあれば教えて下さい...。


さらに高速な複数文字列パターン検索のために

Aho-Corasick とは別の(亜種の)アルゴリズム

例えば GNU grep には Commentz-Walter algorthm という Aho-Corasick と Boyer-Moore が合体したようなアルゴリズムが使われていたり、いろいろ考えられいる。より高みを目指すならこれらのアルゴリズムを実装したほうが良いのだろう。

こういう文字列アルゴリズムをいっきに学べる良い本ないかなと思っていたら Flexible Pattern Matching Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences をおすすめされたので買いました。

ところで、これらのアルゴリズムは割りと歴史が長く、モダンなCPUが開発された現代に最適な複数文字列検索アルゴリズムはないのだろうかと思っていたらあった。

Intelの開発している Hyperscan という複数文字列検索のための正規表現エンジンが存在し、ripgrep も SIMD が有効な場合は hyperscan の考えをベースに実装した Teddy というライブラリを使って高速な複数文字列検索を行うらしい。

REGEX SET SCANNING WITH HYPERSCAN AND RE2::SET hyperscan 早そう

Aho-Corasick の高速化

では Aho-Corasick はもうpracticalには役に立たないのかというとそんなことはなく、Aho-Corasick にはまだ高速化の余地があるようです。

例えば、今回実装したプレーンなAho-Corasickでは状態遷移部分をHashMapを使って実装していたが

We do still have a few tricks up our sleeve though. For example, many Aho-Corasick implementations are built as-if they were tries with back-pointers for their failure transitions. We can actually do better than that. We can compile all of its failure transitions into a DFA with a transition table contiguous in memory. This means that every byte of input corresponds to a single lookup in the transition table to find the next state. We never have to waste time chasing pointers or walking more than one failure transition for any byte in the search text. https://blog.burntsushi.net/ripgrep/


暇があれば Aho-Corasick の高速化や Commentz-Walter の実装と比較。また hyperscan について調べたりしてみたいな。 俺たちの高速文字列検索はまだまだこれからだ!

MtG Arena で学ぶ英語 - mono black aggro?

一年くらい前からMtG Arenaで遊んでいます、今は日本語UIあるのだけれど、いつ海外でデュエリストに襲われても意思疎通ができるように英語UIで英語のカード名に慣れようと、英語UIで遊び続けています。MtG、意外と知らない英単語たくさん出てくるので勉強になる。

ところでこのデッキを見てくれ、こいつをどう思う?

mtgarena.pro

低マナ帯とクリーチャー除去とで固めたデッキで、クリーチャー主体のデッキに対しては結構勝てる。知らない英単語結構見当たるので調べていこう。

Disfigure

gatherer.wizards.com

日本語: 見栄え損ない

Gutterbones

gatherer.wizards.com

日本語: どぶ骨

Knight of Ebon Legion

gatherer.wizards.com

日本語: 漆黒軍の騎士

Footlight fiend

gatherer.wizards.com

日本語: 脚光の悪鬼

Lazotep Reaver

gatherer.wizards.com

日本語: ラゾテプの肉裂き

  • reave
    • 強奪する/盗む
    • Urban Dictionary: Reave
    • 検索ヒット数とか、cambridge 辞書にないのを見るとあまり使われない言葉なのかも

Orzhov Enforcer

gatherer.wizards.com

日本語: オルゾフの処罰者

Priest of Forgotten God

gatherer.wizards.com

日本語: 忘れられた神々の僧侶

特に難しい言葉はないけどpriestの関連語彙

  • priest: 僧侶
  • monk: 僧
  • cleric: 聖職者
  • father: 神父
  • pastor: 牧師

Midnight Reaper

gatherer.wizards.com

日本語: 真夜中の死神

  • reaper
    • reapは元々"刈る"という意味
    • 転じて今では reaper で死神という意味になってそう(reaperで画像検索すると死神の画像しか出てこない)
    • 死神 / 殺し屋
    • Grim reaper: 死神

Drag to the Underworld

gatherer.wizards.com

日本語: 死の国への引き込み

Rankle, Master of Pranks

gatherer.wizards.com

日本語: 悪ふざけの名人、ランクル

prank video でドッキリビデオの意味になる: こういうの↓

理想の家族〜

Spawn of Mayhem

gatherer.wizards.com

日本語: 騒乱の落とし子

京都の観光地の大混雑具合に対して it was mayhem って言ってるのも聞いたことある。

2019年12月と2020年1月のOSS活動記

  • レビュー結構やってました
  • 英会話とか仕事がちょっと忙しかった
  • metals結構わかってきた。

scalameta/metals #1174 Sort auto-completed exhaustive match'es by declaration order

sealed abstract class Test
case object Foo extends Test
case object Bar extends Test
case object Baz extends Test

// ...

def test(t: Test) = t match
//                    ^ ここで補完すると

// 補完後
def test(t: Test) = t match {
  case Foo => // move cursor to here
  case Baz =>
  case Bar =>
}

となる機能が元からあったのだけれど、このcaseの順序は不定(Scalaのreflection APIが返す順序をそのまま使っている)のたのをそれぞれsubclassの定義順序で返すようにする。地味に便利

  • 割と簡単なタスクだったけれどいろいろ学べたので良い入門タスクだった。
    • このプロジェクトのテストの書き方
    • presentation compiler threadのlife cycle
    • symbol search の cache 戦略 など

tanishiking/scalaunfmt #62 Introduce github actions

自分のScalaプロジェクトのCIをgithub actionsに移行しました。完。

scalameta/metals #1213 Fix scaladoc for methods in Completions

後続のPR出すためにmetalsのコード読んでたらscaladocがミスってるやつあったので修正

scalameta/metals #1250 Support scaladoc auto completion on type /**

/** までタイプした時点で、隣接するメソッド定義やクラス定義に対応するscaladocを自動生成する機能

def foo(x: Int, y: Int)(implicit ctx: Context): Int = ???

/**
  * | <- move cursor to here
  *
  * @param x
  * @param y
  * @param ctx
  * @return
  */
def foo(x: Int, y: Int)(implicit ctx: Context): Int = ???

typescript使っててめちゃ便利だなと思ってた機能、実装するときはtypescriptとvscodeの実装を読んでそれを参考にした。

(tsserverはlsp実装してないのでそこらへんの読み替えは必要(ほかはしてる?少なくともこの補完では textDocument/completion 使わずに全部commandでやりとりしている))

方針としては

  • /** をうったら textDocument/completion が発火するようにする
  • 編集中のファイルをcompilation unitに追加、追加前に /** に対応する */ をカーソルの直後に追加した状態でcompilation unitに追加することで、/** 以下のコードがコメントアウトされないようにしてるのが可愛いポイント
  • unitから取得したASTをtraverse、記入中の /** 以下で一番近いメソッド/クラス定義を補完対象とする。
  • scalacのsymbol APIを使って対応するメソッドをすべて取得して completion result をいい感じに生成して返す。

細かい部分の気遣いもよくやってる

  • clientSnippet対応してないクライアントでもインデントがちゃんと揃うように
  • return type が Unit なら @return は追加しない。
  • def foo[T: Ordering](t: T) とかの場合、parse時に (implicit evidence$0: Ordering[T]) みたいなparamが暗黙的に追加されるのを取り除く
    • 本来は evidence$0 には SYNTHETIC flag がついてるはずなのだけれど、parse phase -> typer phase の段階でsynthetic flagが消滅するっぽいことをscalacのコードを読んで調べる。
    • コメントにworkaroundですよって書いておく。scalac側にissue立てようと思ってるけどそんなに直すモチベーションは少ない...

scalameta/sbt-scalafmt #78 Implement error method with an additinal error message and cause

  • sbt-scalafmtが一部条件でエラーメッセージを握りつぶしていて、バグ修正しようにもなんのヒントもない状態だったので、エラーメッセージを握りつぶさないようにする。
  • sbt-scalafmt 2.3.1 リリースした後 sonatype から jar 取得できるようになるまでに2日くらいかかったんだけどなんか障害でもあった?

scalameta/scalafmt #1656 Enable to download and run snapshot version from dynamic

  • レビューしてたら、 2.2.2-SNAPSHOT みたいなscalafmtをローカル環境で実行できないことに気づいたので修正
  • 雑なregexでscalafmtのバージョンパースしてるけど意外とうまくいってる

SOUTH PARK S23E07 S23E08 (英語学習メモ)

S23E07 Board Girls

southpark.cc.com

最近よく話題になるF2Mによる女性向け競技会への出場に関する話。サウスパークジェンダー論の話が結構多いので勉強になるな。 The Cissy - Full Episode - Season 18 - Ep 03 | South Park Studios もめちゃ良かった。

www.bbc.com

www.bbc.com

F2M競技者は試合前にテストステロン値を一定以下に保っておく必要があり、それにより競技の公平性を担保しているけれど、やはりまだ競技会において不平等感を拭えないでいるし、それを表明すると袋叩きにされるみたいな状況らしい。

f:id:tanishiking24:20200102022047p:plain
https://southpark.cc.com/full-episodes/s23e07-board-girls 2週間前に性自認が女性だとして女性競技会に乗り込んできたヘザー

I'm gonna smoke competition

週末にある女性アスリートのためのスポーツ大会に向けて追い込むStrong Woman

No, because Mulan is a female that identifies as male and yet the movie doesn't take the time to address real trans issues. - Ok, Ok! we know "Mulan" is outdated in creating straw dog characters to talk about trans issues.

Disney+ を見ていた PC babies、ムーランが流れ始めて(political incorrectな面があったのか)泣き始める

ムーラン見たことないのだけれど、トランスに関して political incorrect な描写が含まれてたりするのだろうか

We've really come a long way breaking down gender binary bigotry, and I hope I can especially inspire some of my girl students here or those who identify as girls.

en.wikipedia.org

trans以外にも自分の性自認がどちらのgender binaryにも属していない人のことをnon-binary genderという

voguegirl.jp

She is not exactly your average trans athlete. - Well, what is average trans athlete. Honestly I find that kind of bigoted, David.

It is unfair, it is tyrannous, and it is wrong. Ever since these girls were allowed to join Dice Studz Gamers Club, it has been a train wreck.

学校が男女平等を掲げた結果、女子たちがボドゲクラブに参加するようになったことを抗議するカートマン

Well, if you want something hard, then you need a really crunchy Euro game, something like a Vital Lacerda's "Escape Plan," or a Uwe Rosenburg euro. - Do they involve math? - Well, all euros are pretty mathy.

難しいボドゲを遊んで女子たちを追い出そうと画策するカートマンに対して、難しいボドゲなら...とオタク特有の早口で解説を始めるスタン。スタンボドゲ好きだったのね。

I don't know why she has such a grudge against you but ...

テレビ取材に出てまでStrong Womanにつっかかってくるヘザーに対して

Because you went through puberty as a male so your body is completely different.

F2Mの女性競技に対する参加への一般的な反対意見

Since they were born we've taught them to accept and fight for those who are marginalized, that there's no grey area when it comes to inclusion and acceptance.

they とは PC babies のこと。上の発言(Because you went through puberty as a male so your body is completely different)をテレビの前でヘザーに対してしたことにより、PC babiesに顔向けできないというPC principal

Ok, so then let's do it bitch - Oh it's on!!!

全てにおいて世界最強の女はこの俺だというヘザーに対して、ボドゲで私らには勝てないというニコルによる煽りを受けて、ボドゲ勝負に挑むヘザー

f:id:tanishiking24:20200102020706g:plain
https://southpark.cc.com/full-episodes/s23e07-board-girls

このシーン好き

They realize that raising a gender-based issue of strength doesn't necessarily make one a bigot or a bully. All this time, we were worried what the PC babies would think

この話の結論というか、主張はここなんだろうか。競技会における不公平性を論ずることがタブーのようになってしまっていることに対する皮肉

  • 競技の2週間前に女性としての性を辞任したとして女性競技に乗り込み、あらゆる賞をかっさらっていったヘザーに対して、育ってきた性による筋肉量などの違いにおける不公平性を議論に持ち出したPC principal
  • その不公平性を論ずることは gender based bigot や bully ではないというニュアンスをPC babies が理解してくれるか不安がっていたが、PC babiesはそのnuanceも理解してくれたとのこと

めでたしめでたし


S23E08 Turd Buglers

まじで汚いので食事中に見るべきじゃなかった...

southpark.cc.com

All of us have trillions of microscopic critters that grow on and inside our bodies

We do this with a fecal transplant. We'll get a donor's feces, mix it with water, and put it up your mom's anus.

Kyleの母の感染症を治すため、善玉菌を体内で育てる。そのためにfecal transplantを行うと説明する医師。

You're looking chipper today.

f:id:tanishiking24:20200102173706p:plain
https://southpark.cc.com/full-episodes/s23e08-turd-burglars

元気そうなBradley夫人

No I did it myself with a turkey baster.

(Kyle母のfeceを盗んで)自分でFecal Transplantを行ったというBradley夫人、Turkey basterを使って。

  • turkey baster
    • 七面鳥などに肉汁をかけなおすための大きなスポイト
    • 人工授精の道具としても使うらしい(?)

Two face b*tch, you know what she said about you at lunch? - What? - She called you the C-word.

Bradley夫人がいなくなった途端に悪態を付き始めるバターズ母とクレイグ母

Someone in this school is a little turd burglar, and I want some answers. - How can we answer that to which we have no knowledge?

Girls this was all my fault. I think I got a little carried away bragging about my fecal transplant.

carried away bragging about my fecal transplant: 我を忘れてfecal transplantの良さを吹聴しまくった(からみんなDIY fecal transplantに手を出し始めたり他人の糞を盗んだり)

SOUTH PARK S23E05 S23E06 (英語学習メモ)

S23E05 Tegridy Farms Halloween Special

southpark.cc.com

ハロウィン回

What you are seeing here are original knots which were joining the main pieces of the kufu boat.

古代エジプトの博物館の職員による解説

The cedar timbers of the boat's hull were lashed together with hemp rope

hempと聞いて古代エジプトの人々も大麻を使っていた、生活で重要な役割を担っていたと娘のシェリーに解説するランディ(別にハイになるために使ってたわけじゃないのに)

Sarcophagus and mummified remains of Egyptian royalty.

展示内容を読み上げるバターズ

f:id:tanishiking24:20191228141911p:plain
https://southpark.cc.com/full-episodes/s23e05-tegridy-farms-halloween-special

I cant let her problems with marijuana drag me down anymore.

マリファナが嫌いだと言うシェリーにうんざりするランディ

Furniture polish, paint thinner, and bleach. Ammonia and antifreeze one tablespoon each.

ランディの大麻ビジネスを潰すために謎の毒薬を調合するシェリ

  • furniture polish
    • 家具の艶出し薬
  • paint thinner
    • シンナー
  • bleach
    • 漂白剤
  • antifreeze


Shelley's Brew - South Park - "Tegridy Farms Halloween Special" - s23e05

So with this eldritch potion, and these ancient words, I make my revenge upon all the turds.

The mummy says you two got in some kind of altercation last night.

深夜バターズの家に突然押しかけてきた(蘇った)マミー

Now, I don't want to see any fucking sombreros! ... There will be no HOBOS or BUMS, anything depicting people from low-income households. And lastly, heed my fucking words, if I see any of you girls dressed as fucking Moana, I am gonna lose my fucking mind!

ハロウィンの仮装についてのレギュレーションについて説明するPC Principal、他人種を模倣するようなコスプレは文化を踏みにじることになりうるのでやめろとキレ気味に説明する

モアナのコスプレを禁じてるのはこのニュース関連

www.afpbb.com

I just think maybe a night in jail is the wake-up call that she needs.

ランディの大麻ビジネスを邪魔するシェリーに対して一晩牢に閉じ込めておくのは、良い反省になるだろうと嘆願して、娘を投獄するランディ

f:id:tanishiking24:20191228150721p:plain
https://southpark.cc.com/full-episodes/s23e05-tegridy-farms-halloween-special

Wow, we're almost out, Rnady. I gotta go to the barn and get some more! - Okay, I'll hold down the fort.

娘を投獄してる間にTowellyと大麻を売りさばくランディ


S23E06 Season Finale

southpark.cc.com

When I look out on this congregation, I can't help but think "There's not a whole lot of people here." Doesn't seem like a big deal. Nobody's outraged because it was our family.

息子を交通事故でなくなったホワイト家の父、お葬式でのスピーチ

息子の葬式に人々があまり訪れないのは、我々がホワイト家だからだと主張する(ホワイト家がサウスパークから蔑ろにされているのはS21E10あたりから)

f:id:tanishiking24:20191228152354p:plain
https://southpark.cc.com/full-episodes/s23e06-season-finale

Duddy is in police custody until there's a hearing.

ランディが警察に拘束されていることを(悲しそうなふりをしながら)スタンとシェリーに話すシャロン

Did you tell everyone you didn't do anything wrong?... Well, did you then go on the attack, and swap the accusations, to make yourself a victim? Oh, geez, DARVO, Randy -- deny, attack, reverse victim and offender. Alright, let's role play.

留置所にぶちこまれてしまったランディ、屁理屈であらゆる議論を圧倒する(アメリカ)ギャリソン大統領に電話で助けを求める。トラ○プ大統領のやり方がいつもこうだと言わんばかり。

  • DARVO
    • Acronym of “Deny, Attack, and Reverse Victim and Offender”
    • The perpetrator or offender may Deny the behavior, Attack the individual doing the confronting, and Reverse the roles of Victim and Offender such that the perpetrator assumes the victim role and turns the true victim -- or the whistle blower -- into an alleged offender. This occurs, for instance, when an actually guilty perpetrator assumes the role of "falsely accused" and attacks the accuser's credibility and blames the accuser of being the perpetrator of a false accusation.

    • What is DARVO?

Look, I', sorry if you don'y want to talk about it, but have you thought about what you might do if Randy gets put away? - Yeah, I've kind of made a list of all the things I might do.

ランディがいなくなったらどうするか考えたことある?とシャロンに聞く、トークン婦人

Maybe this is your wake-up call that you've been abusing drugs, and you need to face all your wrong-doings, try to turn your life around.

marijana中毒になったランディ、拘置所の医者にマリファナをくれとせがむが、医者はdrugから距離を置くことは、ドラッグの乱用という悪事に目を向けRandyの人生を好転させるのに良い機会だという。

The President of the United States today called the allegations against Randy Marsh "total butt○ucking bullshit" and claims the neighbors who came forward with the evidence video are "Te○pon Faced ○9ing whistleblowers"