algorithm - PATRICIA に一番似合う姓は Crit-Bit かも : 404 Blog Not Found
2013年02月14日04:30 カテゴリアルゴリズム百選Math algorithm - PATRICIA に一番似合う姓は Crit-Bit かも 高速文字列解析の世界 岡野原大輔 「高速文字列解析の世界」を読んだら、熱がぶりかえしてきたので。 ハッシュテーブルや平衡二分木に代わる連想配列を実装するにはどうしたらよいのかという、知恵熱が。 すべてのハッシュ衝突を、生まれる前に消し去りたい。すべての宇宙、過去と未来の全てのハッシュ衝突を、この手でなくてもいいから。 ハッシュテーブル - Wikipedia ハッシュテーブル (hash table) は、キーと値の組（エントリと呼ぶ）を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。ハッシュ表ともいう。ハッシュテーブルは連想配列や集合の最も効率的な実装のうち1つである ハッシュテーブルはあまりに愛用されてきたため、連想配
John Resig - JavaScript Trie Performance Analysis
After my last post discussing dictionary lookups in JavaScript the unanimous consensus seemed to be that utilizing Trie would result in additional space savings and yield performance benefits. A Trie is a relatively simple data structure. At its simplest form you’re building a tree-like structure where each final leaf results in a complete word. This allows for some very efficient use of file size
Nicolas Lehuen (@nlehuen) | Twitter
Unmute @nlehuen Mute @nlehuen Follow Follow @nlehuen Following Following @nlehuen Unfollow Unfollow @nlehuen Blocked Blocked @nlehuen Unblock Unblock @nlehuen Pending Pending follow request from @nlehuen Cancel Cancel your follow request to @nlehuen Nicolas Lehuen @nlehuen Software Engineer, Science Addict, Gaming Enthusiast, Lego Nostalgic, Googler.
Trieではてなキーワード自動リンク - odz buffer
pytstを使ってはてなキーワード自動リンク。全部 Unicode でやりたかったけど、pytst が unicode オブジェクトを扱えないらしくとりあえず、内部は全部 UTF-8 の str で。 例のdartsを使ったやつと違って一応大文字小文字を区別しないマッチングをするようにしてある。 ちなみにこの間抽出したのを使って 400KBytes くらいのファイルに試したら Perl ではてなキーワード自動リンクAPIの正規表現版をそのまま使ったやつの10倍くらい早かった。 import urllib import tst class KeywordAutoLinkCallback: def __init__(self, original_text): self.buffer = "" self.original_text = original_text self.offset = 0
Trie
トライのノードをビット列(e.g. 00011000)と思って、それを いかに最適に重ねあわせるかという話をしている。他の方式 の可能性については議論していない。Greedyに順番に入れ ていくと最適にならない場合があるから最適のものをみつ けるには時間がかかる。(当然)
Darts: Double ARray Trie System
Darts: Double-ARray Trie System はじめに Darts は, Double-Array [Aoe 1989]を構築するための シンプルな C++ Template Library です. Double-Array は Trie を表現するためのデータ構造です. ハッシュ木, デジタルトライ, パトリシア木, Suffix Array による擬似 Trieといった 他の Trie の実装に比べ高速に動作します. オリジナル の Double-Arrayは, 動的に key の追加削除を行えるような 枠組ですが, Darts は ソート済の辞書を一括してDouble-Array に変換することに機能を絞っています. ハッシュのような単純な辞書として使うことも可能ですが, 形態素解析器の辞書に必須の Common Prefix Search を非常に高速に行うことが
横着プログラミング 第6回: chatty: 小うるさい端末
最終更新日: 2002-09-18 (公開日: 2002-09-18) Unix Magazine 誌に 2002年1月号から 2003年2月号にかけて連載し ていた記事の元の原稿です。 才気に富んだことは個人が行うのが通例であり、信じがたきバカ さ加減は大抵組織に帰されるものである。 -- Jon Bentley *1 役に立たないソフトウェアを作るのが好きだ。面倒な作業を楽にす る横着ソフトウェアもいいが、たまには人を呆れさせるくだらない ソフトウェアを作るのも楽しい。 以前に私が開発した cdbiff*2というソフト ウェアは、メールが届くと PC の CD-ROMドライブが開いてメール の到着を通知するという役に立たないものであったが、そのくだら なさが受けて予想外の好評を得た。今回は、そうした役に立たない ソフトウェアの 1つである、小うるさい端末 chatty*3 を紹介する。
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
