ボイヤー-ムーア文字列検索アルゴリズム - Wikipedia
テキスト T = "ANPANMAN" に対して k = 3 から k = 8 までパターン P = "PAN" を配置した様子。この場合、k = 5 の位置で一致する。 文字列 S に対する操作を以下のように表す： S[i]： 文字列 S の i 番目の文字 S[i..j]： 文字列 S の i から j 番目までの部分文字列（i 文字目、j 文字目をそれぞれ含む） 文字列 S に含まれる文字の個数を文字列の長さと定義する。また、文字列 S の先頭を含む部分文字列をプレフィックス、末尾を含む部分文字列をサフィックスと定義する。 len(S)：S の長さ S[1..i], 1 ≤ i ≤ len(S)：S のプレフィックス S[i..len(S)], 1 ≤ i ≤ len(S)：S のサフィックス 検索文字列をパターンと呼び、P で表す。被検索文字列をテキストと呼び、T で表す。また T
接尾辞配列 - Wikipedia
接尾辞配列（せつびじはいれつ）やサフィックス・アレイ（英: suffix array）とは、文字列の接尾辞（開始位置を異にし終端位置を元の文字列と同じくする部分文字列）の文字列中の開始位置を要素とする配列を、接尾辞に関して辞書順に並べ替えて得られる配列である。接尾辞木の配列版。主に文字列探索、全文検索などに利用される。1990年に Udi Manber と Gene Myers が発表した[1]。
FF12の乱数について
概要 FF12が内部でどのように乱数を扱っているか調べたので、分かったことを書くよ。 目次 概要 表記 注意 導入 生成器Aの特徴 A系列のよくある利用パターン A系列を使う処理 銃 素手 斧、ハンマー、ハンディボムによる攻撃のダメージ計算 ケアル、ケアルダ ポーション、ハイポーション、エクスポーション、エーテル、ハイエーテル トレジャーの開封 セーブデータのロード A系列の乱数を消費しない行動 応用例 乱数位置の特定 5hits法の原理 "セロビ台地/交差ヶ原"のトレジャーPOP法則 分かっていないこと 表記 この文章では以下の規則に従う。 ⌊x⌋で、x以下の整数のうち最大のものを表す。 x % yで、xをyで割った余りを表す。x % y = x - y * ⌊x / y⌋ 注意 この文章では、FF12内の乱数の規則性を観察し、それを制御する方法について述べている。こういうプレイははおそ
Bloom filterの説明 — ありえるえりあ
Bloom filterの説明 以前、bloom filterに言及したことがあるのですが、実は、言及しただけで何も調べていませんでした。 来週、ある人の話を聞く時、知らないとついていけない可能性があるので、調べてみました。 - 参考サイト 感想ですが、予想以上にシンプルでした。 動作イメージ(だけ)は誰でもイメージできます(実装も簡単)。 上の参考サイトも、英語に気後れせず、図だけでも見てください。動作は想像できるはずです。そして、たぶん、その想像は当たっています。 参考サイトを読めば分かることを日本語で改めて説明するのも気がひけますが、どうしても英語を読みたくない人のために、簡単に説明してみます。 動作イメージ あ る入力文書が与えられたとして、後で、その文書に、ある単語fooが存在するかを高速にチェックしたい、という問題を想定するのが理解しやすいと思いま す。入力文書に対する前処理を
開発メモ: トップNソートの検討
上位N件をソートした状態で取り出すという、いわゆる「トップNソート」の効率的な実装について検討してみた。 背景 データベースに対して、ある順序でソートした時の最初の何件かが欲しいというクエリを投げることはよくあるだろう。SNSで言えば、誰かのコンテンツの最新10件を表示するとかいう場合だ。SQLだと "ORDER BY xxx LIMIT yyy" とかいう感じ。同じような操作は全文検索システムのスコアリングでも定番である。俺もよく自分で実装するわけだが、その度に適当な試行錯誤をして時間がもったいないので、今回は入念に調べて決定版を出そうじゃないか。 全体をソートして上位を取り出せば目的は満たせるのだが、それだと無駄な計算が多い。100万件の中から上位10件だけ欲しい場合に、残りの99万9990件まで律儀にソートする必要はない。ということで、上位N件をソートして取り出すという「トップNソー
algorithm - 最近点検索をkd-treeで : 404 Blog Not Found
2009年04月30日01:00 カテゴリMathLightweight Languages algorithm - 最近点検索をkd-treeで というわけで、kd-treeによる検索も実装してみました。 はてなブックマーク - ototoiのブックマーク データ数が少ない場合、この全検索が高速。ただデータが多くなってくるとkd-treeがいいと思う。点ならば配列をソートするだけで実現できる。 以下のデモでは、単にkd-treeによる検索だけではなく、kd-tree構築の速度と、総当たりの場合の速度の比較もできるようにしてあります。10,000点ぐらいだと、その差を顕著に感じることが出来るでしょう。100,000点ぐらいあると、感動的なほど差が出ます。それだけあってもkd-treeの方はほぼ1ms以内に検索が終わるのですから(ただしこの場合、デモの実行に合計10秒以上かかるので注意!)。
DHTのアルゴリズム - WebLab.ota
分散ハッシュテーブル - Wikipedia DHTは、ピュアP2Pであってもネットワーク負荷はそれほど上がらず、ネットワーク上のコンテンツを漏れなくかつ高速に探索することを可能にする。従来のピュアP2Pで採用されていた通信では、数10万ピアぐらいが限界だとされているが、DHTを使うと数10億ピアを探索範囲とすることが可能となる。しかし、実装がむずかしいことが欠点となる。 DHTの欠点は、一般的に完全一致探索しか行えないことである。特に正規表現のような複雑な検索をDHTのみで実現することは不可能である。 代表的なDHTのアルゴリズムを説明している日本語文献を探してみた． Chord この節では，DHT の代表的なアルゴリズムであるChord について説明する．Chordのハッシュ空間上での距離の定義は，ハッシュ値の差の絶対値である．図3.5のように，データ保有ノード (図中の青点) を，そ
ConsistentHashing - コンシステント・ハッシュ法
ConsistentHashing - コンシステント・ハッシュ法 目次 この文書について コンシステント・ハッシュ法 実例 実装 用途 コンシステント・ハッシュ法 この文書について "Tom White's Blog: Consistent Hashing" の日本語訳です. http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html 推敲歓迎: 誤訳, タイポ, 訳語の不統一, そのほか... 原文のライセンス: http://creativecommons.org/licenses/by-nc-sa/2.0/ 私は今までに何度かコンシステント・ハッシュ法にとりくんだことがある。 このアイデアをあらわした論文 ( David Karger らによる Consistent Hashing and R
【レポート】GNU grepが高速な理由 | エンタープライズ | マイコミジャーナル
FreeBSD - The Power To Serve why GNU grep is fast (なぜGNU grepは高速なのか)といったタイトルの興味深いメールがFreeBSD開発者メーリングリストに投函された。メールを出したのはGNU grepのオリジナル開発者であるMike Haertel氏。Mike Haertel氏はFreeBSDユーザでもあり、FreeBSD開発者メーリングリストで興味深いやりとりがあったため、このメールを流したとしている。Mike Haertel氏の紹介する内容はgrep(1)の実装のみならず、高速な文字列処理を実現するひとつの方法として参考になる。紹介されているGNU grep高速さの秘訣は次のとおり。 GNU grepは入力バイトのすべてをチェックするようなことは避けている。 GNU grepはバイトごとに適用する操作を極力最小限に減らしている。 G
Fisher–Yates shuffle - Wikipedia
Example of shuffling five letters using Durstenfeld's in-place version of the Fisher–Yates shuffle The Fisher–Yates shuffle is an algorithm for shuffling a finite sequence. The algorithm takes a list of all the elements of the sequence, and continually determines the next element in the shuffled sequence by randomly drawing an element from the list until no elements remain.[1] The algorithm produc
trigonometric calculation by CORDIC
CORDIC による三角関数の計算 この手の解説の最初にありがちな、CORDIC ってなんの略でしょう、 などという話は飛ばして、いきなり本題に入ります。 とりあえず、x の余弦や正接、つまり cos x や tan x が求めたいものとします。 また、三角関数の周期性を使って、 x は 0 から 45 度の間に正規化されているものとします。 また, 基本的な一次変換の知識を仮定しています。 突然ですが、問題です。コンピュータや電卓を使わずに、 人様が任意の角度の三角関数の値を求めるには、 どうするでしょうか。 答え）高校の数学の教科書にもあるように、 適当な基準線から分度器を使って求めたい角度を持つ直角三角形を書き、 その三辺の長さをはかって割り算をする。 ということで、この考えを応用したのが CORDIC です。 とりあえず、基準線の方向として、x 軸上の点 P0(1,0) から出発し
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
M.Hiroi's Home Page / Lightweight Language