Fast and Easy Levenshtein distance using a Trie
Only the last row changes. We can avoid a lot of work if we can process the words in order, so we never need to repeat a row for the same prefix of letters. The trie data structure is perfect for this. A trie is a giant tree, where each node represents a partial or complete word. Here's one with the words cat, cats, catacomb, and catacombs in it (courtesy of zwibbler.com). Nodes that represent a w
情報処理学会論文誌．プログラミング (PRO 51) 1 最適化 Packrat Parser の 空間計算量の計算手法の提案 ○ 水 島 宏 太†1 前 田 敦 司†1 山 口 喜 教†1 従来主流の構文解析手法である LL や LR 法��
情報処理学会論文誌．プログラミング (PRO 51) 1 最適化 Packrat Parser の 空間計算量の計算手法の提案 ○ 水 島 宏 太†1 前 田 敦 司†1 山 口 喜 教†1 従来主流の構文解析手法である LL や LR 法の欠点を解決する構文手法の一つとし て packrat parsing という構文解析手法が注目を集めている．packrat parsing は， parsing expression grammar (PEG) という形式文法で表現できる任意の言語を扱 うことができ，これは LL 法や LR 法よりも強力である．また，packrat parsing で は解析を線形時間で行うことができる．しかし，packrat parsing では，構文解析の 中間結果を全てメモ化するため，メモリ使用量が線形になってしまうという欠点があ る．我々の研究では，カット演
pyPEG – a PEG Parser-Interpreter in Python
IntroductionPython is a nice scripting language. It even gives you access to its own parser and compiler. It also gives you access to different other parsers for special purposes like XML and string templates. But sometimes you may want to have your own parser. This is what's pyPEG for. And pyPEG supports Unicode. pyPEG is a plain and simple intrinsic parser interpreter framework for Python versio
gengo3.ppt
1 • 形式言語 – 有限オートマトンと正規文法 – 正規文法の限界と文脈自由文法 – PDA • 生成規則による言語の能力の違い 0型言語 0型文法 チューリングマシン 1型言語 文脈依存文法 線形拘束オートマトン 2型言語 文脈自由文法 プッシュダウンオートマトン 3型言語 正規文法 有限オートマトン 文法 オートマトン <=等価=> (汎用計算機) 能力大 能力小 4 • 最も制約された文法 (regular grammar) – 生成規則 • ポイント a (文字) を必ず含む – 規則と生成する文字列との関係 例) 「平成□□年」を受け付ける正規文法 ={S，Y, A} ={平成，年，1,2,.., 21} σ= S P={S平成 Y, Y 1 A, Y 2 A, Y 21 A, A
Parsing Expression Grammar - Wikipedia
Parsing Expression Grammar（PEG）は、分析的形式文法の一種であり、形式言語をその言語に含まれる文字列を認識するための一連の規則を使って表したものである。PEGは再帰下降構文解析を文法を示すためだけに純粋に図式的に表現したものと見ることもでき、具体的な構文解析器の実装やその用途とは独立している。 PEGにおける構文（文法）の定義は文脈自由文法のバッカス・ナウア記法によるそれに似ているが、文脈自由文法では一般に「｜」（縦棒、バーティカルバー）で表される「これらのうちどれか」ではなく、「最初の解析がうまくいったらそれを、失敗なら次を順に試してゆき、成功したものを採用」（「/」であらわす）という意味を使う。 このため、文脈自由文法とは異なり、PEGには曖昧さは存在しない。文字列を構文解析する場合、正しい構文木は常に1つしかない。このためPEGはコンピュータ言語の構文解析
この機会にマスターしようぜ、正規表現、構文図、オートマトン - 檜山正幸のキマイラ飼育記 (はてなBlog)
正規表現と構文図について解説します。オートマトンについても詳しく述べます。オートマトン・スゴロクで遊びましょう！ 世間でよく知られている／使われている概念・方法にはこだわらず、僕（檜山）の感覚で一番わかりやすいと思われる筋書きと用語法／図式法を使って説明します。この記事に目を通して“感じ”が掴めたら、形式言語理論の教科書を読み始めることが出来るでしょう。 [追記]この記事の内容に対する具体例は、「正規表現とオートマトン：なんだ簡単じゃん、JavaScriptによる実装」にあります。[/追記] 内容： 正規表現 正規表現の例 構文図 基本記号 連接 選択 省略可能 繰り返し ストレートワイヤーによるレイアウト調整 有限状態オートマトン 有限状態オートマトンの実行 バックトラックと先読み スゴロクとオートマトン コマをたくさん使うスゴロクと並列処理 非決定性オートマトンと決定性オートマトン 正
N-gram コーパス - 日本語ウェブコーパス 2010
概要 ウェブページに出現する形態素 N-gram と文字 N-gram を頻度とともに収録したコーパスです．各 N-gram コーパスには，頻度 10/100/1000 以上の 1-gram から 7-gram までが収録されています． N-gram コーパスの構築においては，Google N-gram コーパスと同様の前処理を施しています．句点・感嘆符・疑問符を文の区切りとして利用しているので，「モーニング娘。」や「Yahoo!」などの固有名詞については，不適切な文の区切りがおこなわれています．また，文の区切りは削除するようになっているため，コーパス中に句点・感嘆符・疑問符は出現しません． 形態素 N-gram コーパス，文字 N-gram コーパスともに，文境界マーク（<S>，</S>）は採用していますが，未知語トークン（<UNK>）は採用していません．また，文字 N-gram コーパ
Repetition Visualizer
This tool visualizes runs, squares or palindromes in a string.
大規模データで単語の数を数える - ny23の日記
大規模データから one-pass で item（n-gram など）の頻度を数える手法に関するメモ．ここ数年，毎年のように超大規模な n-gram の統計情報を空間／時間効率良く利用するための手法が提案されている．最近だと， Storing the Web in Memory: Space Efficient Language Models with Constant Time Retrieval (EMNLP 2010) とか．この論文では，最小完全ハッシュ関数や power-law を考慮した頻度表現の圧縮など，細かい技術を丁寧に組み上げており，これぐらい工夫が細かくなってくるとlog-frequency Bloom filter (ACL 2007) ぐらいからから始まった n-gram 頻度情報の圧縮の研究もそろそろ収束したかという印象（ちょうど論文を読む直前に，この論文の7節の
Python による日本語自然言語処理
はじめに この文書は、 Steven Bird, Ewan Klein, Edward Loper 著 萩原 正人、中山 敬広、水野 貴明 訳 『入門 自然言語処理』 O'Reilly Japan, 2010. の第12章「Python による日本語自然言語処理」を、原書 Natural Language Processing with Python と同じ Creative Commons Attribution Noncommercial No Derivative Works 3.0 US License の下で公開するものです。 原書では主に英語を対象とした自然言語処理を取り扱っています。内容や考え方の多くは言語に依存しないものではありますが、単語の分かち書きをしない点や統語構造等の違いから、日本語を対象とする場合、いくつか気をつけなければいけない点があります。日本語を扱う場合にも
Suffix Array(接尾辞配列)を学びたい人のためのリンク集 - EchizenBlog-Zwei
私がCompressed Suffix Arrayを学ぶのに参考にした資料へのリンクをまとめてみた。 CSAだけじゃなく、これからSuffix Arrayを学ぶ人にも便利かもしれない。 解説記事 # ［を］ Perl による Suffix Array の実装] SUFARYの開発者、たつを氏による解説 perlで20行くらいでSuffix Arrayが作れる 入門用におすすめ # DO/Suffix Array 岡野原氏によるSuffix Arrayの解説記事 高速化などの高度な話題が豊富 中級者向け # white page Suffix Arrayのリンク集が充実 多くのライブラリが公開されている ツール・ライブラリ # SUFARY 臨時復旧ページ たつを氏によるSuffix Arrayライブラリ 非常に使い勝手が良い # sary: Suffix Arrayのライブラリとツール 高
MySQL :: MySQL 8.0 リファレンスマニュアル :: 8.3.1 MySQL のインデックスの使用の仕組み
インデックスは特定のカラム値のある行をすばやく見つけるために使用されます。 インデックスがないと、MySQL は関連する行を見つけるために、先頭行から始めてテーブル全体を読み取る必要があります。 テーブルが大きいほど、このコストが大きくなります。 テーブルに問題のカラムのインデックスが含まれている場合、MySQL はすべてのデータを調べる必要なく、データファイルの途中のシークする位置をすばやく特定できます。 これはすべての行を順次読み取るよりはるかに高速です。 ほとんどの MySQL インデックス (PRIMARY KEY、UNIQUE、INDEX、および FULLTEXT) は B ツリーに格納されます。 例外: 空間データ型のインデックスは R ツリーを使用します。MEMORY テーブルはハッシュインデックスもサポートします。InnoDB は FULLTEXT インデックスの逆のリスト
検索の歴史 一文字進化するのに掛かった年数は、なんと… - 当面C#と.NETな記録
文字列の高速検索の歴史を年表にしてみたんだけど、年表にしたらめちゃくちゃおもしろいことに気づいてしまいました！今日のエントリーは必見ですよ！ id:siokoshou:20060323 に書いた EXACT STRING MATCHING ALGORITHMS に各論文の発表された雑誌が載ってたので、年表に並べてみました。いろいろ検索しててあちこちでみかけた名前だけ並べてます。 1977 KMP 1977 BM (Boyer-Moore algorithm) 1980 BMH (Horspool algorithm) 1990 Sunday Quick Search algorithm 1992 Shift Or algorithm 1992 Turbo-BM algorithm (繰り返し対策.DNAのように文字種の集団が小さい場合に有効) んで、注目のポイントはここ。 1980 BMH
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
トークイベント「統計的自然言語処理ーことばを扱う機械」
情報処理学会論文誌. プログラミング 49(SIG 1(PRO 35)), 117-126, 2008-01-15 1 Packrat Parsing のメモリ効率の改善手法 ○ 水 島 宏 太† 前 田 敦 司† 山 口 喜 教† Packrat parsing は，バックトラック付き��
http://sleepyheads.jp/docs/prob_ir.pdf
つぶやきでみる花粉症話題度マップ
Chimaira.org
オートマトンと形式言語 正規文法と正規言語 桔梗宏孝 今日の目標 正規言語は正規表現が表す言語である。 これは有限オートマトン(ε-NFA, DFA)が表す言 語でもあった。 正規文法が生成する�
The Exact String Matching Problem: a Comprehensive Experimental Evaluation