編集距離（レーベンシュタイン距離）の求め方 - 具体例で学ぶ数学
編集距離とは 「すうがく」という単語を最低何回「編集」すれば「すがた」という単語になるでしょうか？ ただし「編集」とは、 一文字挿入、一文字削除、一文字置換 のいずれかの操作のこととしましょう。 例えば、 「すうがく」の「う」を削除 →「すがく」の「く」を「た」に置換 →「すがた」 となり、「すうがく」から「すがた」へは編集２回で行けることになります。（編集１回では行けません） このように、必要な「編集」の最低回数のことを編集距離と言います。 つまり「すうがく」と「すがた」の編集距離は $2$ です。 「編集」で許す操作は、挿入または削除または置換としましたが、置換を許さないなど、他にもバリエーションがあります。 このように「編集」の定義はいろいろありますが、挿入または削除または置換という「編集」による編集距離を、特にレーベンシュタイン距離と言います。 参考：Levenshtein dis
ハッシュテーブルのスロット数が素数がよい理由と誕生日のパラドックス
最近、プログラマーがハッシュテーブルを実装する機会は少ない。 現代のプログラミング言語では、ハッシュテーブルはライブラリーに完備されているためだ。 C言語でも、オープンソースを探せば、良いライブラリーが見つかる。 C言語をよく使う自分は、趣味でハッシュテーブルを自作して来た。 最近またハッシュテーブルを自作して、本質を深く理解できたので、メモしておく。 C言語を学び、ハッシュテーブル、リストなどのデータ格納アルゴリズムを一度は実装して確認することで、コンピューターで大量のデータを取り扱う基本を学ぶことができる。 ハッシュテーブルは、データをキーと値の組で保管するものだ。 キーは、数字ではなく、名前のような文字列や、複数の数値の組み合わせである。 値も複雑なデータの組み合わせとなる。 キーはデータを一意に区別できるものである。 複雑なキー情報に一致する値を素早く探し出すために、ハッシュという
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 を非常に高速に行うことが
簡潔データ構造 LOUDS の解説（全12回、練習問題付き）
「日本語入力を支える技術」（通称「徳永本」）や「高速文字列解析の世界」（通称「岡野原本」）で紹介されている LOUDS というデータ構造を、12回に分けて解説しました。 友達に教える時に使ったもので、練習問題付きです。 実際に紙に書いてやってみるとわかりやすいと思います。 詳解 LOUDS (1) LOUDS とは 詳解 LOUDS (2) ビット列を作ってみる 詳解 LOUDS (3) 0番ノード 詳解 LOUDS (4) ビットの意味 詳解 LOUDS (5) 木構造の復元 詳解 LOUDS (6) インデックスでノードを表す 詳解 LOUDS (7) ノード番号からインデックスを得る 詳解 LOUDS (8) インデックスからノード番号を得る 詳解 LOUDS (9) 子ノードから親ノード 詳解 LOUDS (10) 親ノードから子ノード 詳解 LOUDS (11) 木の検索 詳解
その８ 4分木空間分割を最適化する！
ホーム＜ゲームつくろー！＜衝突判定編 2D衝突編 その８ 4分木空間分割を最適化する！（理屈編） ゲーム空間に置いたオブジェクトを総当りで衝突判定する事ははっきりと非効率だと言えます。ちょっと計算してみましょう。60FPSのゲームの1フリップ約16.6ミリ秒の内衝突判定に10%の時間余裕（1.66ミリ秒）を与えられたとします。もし1000回の衝突判定に1ミリ秒かかるなら（1000回/msec）、判定回数は1660回以下に抑えないと間に合いません。総当りだとこれは58オブジェクトくらいで限界です。判定時間が200回/msecならオブジェクトはたった18個で限界。これはどう考えても節約が無いとゲームになりません。 オブジェクトの全ての位置が決まった時、自分とぶつかる可能性があるのは自分の周りのオブジェクトだけです。遠い所にある物は判定する必要すらありません。そこで「空間をある程度制限してその中
Glibc malloc internal
2. 今日は何の話？ libc でもっとも良く使われる関数、 malloc と free の実装の解説 もっと一般的に言うと、プロセスのアドレス空間のうち、 heap 領域とよばれる、場所を操作する関数の説明 解説というと聞こえはいいが、そんな大層なものじゃない 3. Linux での process address space model kernel stack text mmap data bss heap 矢印はデータ量の増加と ともに、伸びる方向 使用中 使用中 使用中 今日は、ここ、 heap と呼ばれる領域のお話 low high free free free 4. 古典的 malloc プログラミング言語 C （いわゆる K&R) で紹介された初期の Unix の malloc 実装 使用中 使用中 使用中 free listの head 使用中 ・ free list を
転置インデックスの構成とブーリアン検索
転置インデックスの構成とブーリアン検索 2008-01-18-1 [IIR][Algorithm] 「Introduction to Information Retrieval」[1]の第一章[2008-01-12-1] の転置インデックスまわりの用語と検索手順などの解説です。 ちょっと前に書いた 『ウェブ検索を「本の索引」で説明する試み』[2007-06-17-6] という記事の続きでもあります。 「転置インデックスによる検索システムを作ってみよう！」 [2007-11-26-5]もご参考に。 § 転置インデックス (inverted index または inverted file) は、 dictionary と postings の二つの部分から構成されます。 dictionary は索引語 (term) の集合です。 term が登場する文書の ID を posting と呼びます
開発メモ: トップNソートの検討
上位N件をソートした状態で取り出すという、いわゆる「トップNソート」の効率的な実装について検討してみた。 背景 データベースに対して、ある順序でソートした時の最初の何件かが欲しいというクエリを投げることはよくあるだろう。SNSで言えば、誰かのコンテンツの最新10件を表示するとかいう場合だ。SQLだと "ORDER BY timestamp DESC LIMIT 10" とかいう感じ。同じような操作は全文検索システムのスコアリングでも定番である。俺もよく自分で実装するわけだが、その度に適当な試行錯誤をして時間がもったいないので、今回は入念に調べて決定版を出そうじゃないか。 全体をソートして上位を取り出せば目的は満たせるのだが、それだと無駄な計算が多い。100万件の中から上位10件だけ欲しい場合に、残りの99万9990件まで律儀にソートする必要はない。ということで、上位N件をソートして取り出す
高速かつ省メモリなbit vector「sucBV」を作る
はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するデータ構造は「操作付きbit vector（SUCcinct Bit Vector:sucBV）」です。sucBVは、圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。STLのvector<bool>と同様に、bit列情報B[0....n-1]を保存します。このbit列情報は前もって与えられ、変更が無いことを前提とします。sucBVは、次の二つの操作を定数時間でサポートします。 rank(p,bit)――B[0...p]中のbit（bitは1
簡潔データ構造超入門III 〜簡潔ビットベクトルで転置インデックスを効率的に実装する〜 - EchizenBlog-Zwei
前回までで簡潔ビットベクトルというデータ構造を実装した。簡潔ビットベクトルとは普通のビット列に少しの追加データを持たせることでrank/selectという2つの操作が可能にしたもの。そしてrank/selectとはそれぞれ以下の操作のこと。 rank(x) : x番目のビット以前(xの位置を含む)の立っているビットの数 select(i): i番目に立っているビットの位置今回は簡潔ビットベクトルを利用して転置インデックスを効率的に実装してみる。 前回までの記事： 簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei 転置インデックスとは検索エンジンに用いられるインデックスで apple 1, 3 orange 1, 2, 4, 6のように各単
sary: Suffix Arrayのライブラリとツール
saryとは? sary は Suffix Array のライブラリとツールです。Suffix Array と呼ばれるデータ構造を用いることにより、 10MB, 100MB といっ た巨大なテキストファイルに対する高速な全文検索を実現します。 特定の個所だけにインデックスポイントを割り当てることにより、 特定のフィールドのみを検索対象にすることもできます。 目次 新着情報 特徴 Suffix Arrayの簡単な説明 libsaryのリファレンスマニュアル 付属ツールの使い方 FAQ ダウンロード TODO 関連リンク集 メーリングリスト 新着情報 2005-03-30: sary 1.2.0 公開 ABIが変更されました 細かなバグ修正がされました 2002-09-18: sary 1.0.4 公開 検索結果の表示を高速化しました ヘルプメッセージを修正しました 2001-04-20: さ
ビットを数えるアルゴリズム: ふらふら日記
ビットを数えるアルゴリズム by 矢口真里 浮気相手 (06/13) コンスタンティン(劇場) by 寺田誠知 (04/20) 日蝕！ by 幸運の出会いNAVI (02/08) 日蝕！ by 近 距 離 逆 援 セ レ ブ (02/03) 日蝕！ by ご近所メール (01/27) あるビット列があったとき，その中にいくつ1が立っているかを調べるアルゴリズムがありますが，そのアルゴリズムがどうしてちゃんと動くのか考えてみました． http://wiki.livedoor.jp/ngr5_600/d/%A5%D3%A5%C3%A5%C8%A4%F2%BF%F4%A4%A8%A4%EB より int numofbits5(long bits) { bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555); bits = (bits & 0x3
[を] 転置インデックスによる検索システムを作ってみよう！
転置インデックスによる検索システムを作ってみよう！ 2007-11-26-5 [Algorithm][Programming] 転置インデックス[2007-06-17-6]による検索システムの実装は パフォーマンスを無視すれば意外と簡単です。 それを示すために Perl で簡単な検索システムを作ってみました。 検索方式は転置インデックス(Inverted Index)、 ランキングには TF-IDF[2005-10-12-1] を用いました。 検索対象ファイルは一行一記事で以下のフォーマットとします。 [記事ID][SPC][記事内容]\n 記事IDは数字、記事内容は UTF-8 の文字で構成されるものとします。 以下のようなサンプル test.txt を用意しました。 1 これはペンです 2 最近はどうですか？ 3 ペンギン大好き 4 こんにちは。いかがおすごしですか？ 5 ここ最近疲れ
Double-Array Articles
ダブル配列のライブラリを公開しているページです． An Implementation of Double-Array Trie URL: http://linux.thai.net/~thep/datrie/datrie.html Darts: Double-ARray Trie System URL: http://chasen.org/~taku/software/darts/ Dame URL: http://www.void.in/wiki/Dame Tiny Double-Array Library URL: http://nanika.osonae.com/TinyDA/index.html Dynamic Double-Array Library URL: http://nanika.osonae.com/DynDA/index.html
Ruby で Double-Array を実装して Common-Prefix Search を試してみる - P A R A G R A P H S
lib/trie/double_array.rb at master from tily's ruby-gardening - GitHub Double-Array (ダブル配列) は トライ木を実装するためのアルゴリズムの 1 つで、他の実装よりも高速に TRIE から文字列を検索できるらしい。ChaSen や MeCab で、形態素解析を行うために必要な Common-Prefix Search (共通接頭辞探索) を行うために使われている。これを理解のために Ruby で実装してみた。 基本的な動作確認 ここに書いてある bird, bison, cat の 3 単語で構築した Double-Array の例。 コード： require 'trie/double_array' da = Trie::DoubleArray.new da.build(%w|bird bison cat
文字列検索アルゴリズムのAho Corasick法をRubyで適当に実装してみる - grafi-note
Ruby, AlgorithmAho Corasick法は、複数の文字列を高速に検索するアルゴリズムです。簡単に言えばwikipedia:クヌース-モリス-プラット法とwikipedia:トライ木を合わせたようなアルゴリズムで、KMP法ではマッチに失敗した時の位置を表の形で保持しますが、AhoCorasick法ではこれを「failure link」としてトライ木の上に構築します。なお、この木を利用したこのアルゴリズムは決定性有限オートマトンとして機能します。failure linkの指す先は、マッチに失敗した文字列の、先頭の一文字を削った時にマッチする位置に相当します。先頭の一文字を削ってもマッチする位置が無いなら二文字、三文字、と削っていった位置に相当し、何文字削ってもマッチしない場合はルートを指すことになります。検索する際はトライ木同様にルートから一文字ずつノードを辿っていくのですが、
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
