[B! algorithm] yusuketのブックマーク

Pike VMとEarley法の関係についてRubyで実装して考えてみる | makenowjust-labs/blog

正規表現マッチングの実装手法の1つとしてPike VMと呼ばれるものがあります。これはGo言語の正規表現実装やRustのregex crateで使われている手法であり、正規表現rrrと入力文字列wwwに対してO(∣r∣×∣w∣)O(|r| \times |w|)O(∣r∣×∣w∣)の計算量でマッチングができるのが特徴です。 Earley法はJay Earleyの提案した文脈自由文法 (CFG) の構文解析手法の1つです。すべてのCFGを構文解析できる手法で最悪計算量はO(∣w∣3)O({|w|}^3)O(∣w∣3)ですが、無曖昧であればO(∣w∣2)O({|w|}^2)O(∣w∣2)で、決定的であればO(∣w∣)O({|w|})O(∣w∣)で構文解析ができます。実装してみると分かりますが、Pike VMとEarley法には類似している点があり、Earley法をPike VMの発展系の

yusuket 2023/08/08

あとで読む

リンク

テキストエディタで使われがちなデータ構造 Piece Table の概要と実装 - A Memorandum

テキストエディタのデータ構造 Gap method Piece Table method Piece Table の構造 Piece Table の実装 Piece Table のメソッドまとめテキストエディタのデータ構造テキストエディタで採用されているデータ構造にはいろいろあります。こちらの論文 Data Structures for Text Sequences では各種データ構造について比較検討されています。多くは、Gap method や Piece table method をベースにしたものが多いのではないでしょうか(図で言う最下部の中心の丸印に当たります)。最近では Rope なども有名ですね。 Gap method Gap method では、現在のカーソル位置で、テキストバッファを2つに分割し Gap を間に挟み、カーソル位置に対する編集(テキスト追加/削除)を

yusuket 2022/09/14

リンク

典型データ構造まとめ - beet's soil

なんか前回伸びたので参考 hamayanhamayan.hatena blog.jp ei1333's page 宣伝 beet-aizu.hatena blog.com 以下とりあえず辞書順（そのうち典型度順にしたい） Binary Indexed Tree 一点加算、先頭からの区間和、k番目に大きい値がで可能 library/binaryindexedtree.cpp at master · beet-aizu/library · GitHub 容易に多次元に拡張が可能（実用上は2次元くらい？ library/binaryindexedtree2D.cpp at master · beet-aizu/library · GitHub Binary Trie 二進数を管理するTrie木全体にXOR、k番目に大きい値、lower_bound等がで可能 library/binarytri

yusuket 2018/05/08

リンク

文字列アルゴリズムの学びかた - Hatena Developer Blog

こんにちは！はてなアプリケーションエンジニアの id:takuya-a です。みなさんは、このような疑問をもったことはありませんか？ grep はどのように文字列を検索しているのか？ MeCab はどうやって辞書を高速にルックアップしているのか？パーサやコンパイラを作りたいけど、何から始めればいいのか？本稿では、「文字列アルゴリズムとはどんなものなのか？」「なぜ重要なのか？」「何を知っておくべきか？」「どうやって勉強すればいいのか？」といった疑問にお答えしていこうと思います。文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんに