アルゴリズムとデータ構造 演習第 10 回
アルゴリズムとデータ構造 演習第 10 回 サーチ１（二分探索） データの中から、あるデータを探すことを探索といいます。 ここでは二分探索 （アルゴリズムＣ 第２巻 p.8） を用いて探索を行います。 問題１ ［印刷用 PostScript］ 次のようなソートされたデータがある。 1 4 6 9 10 13 19 23 25 30 (1) このデータから二分探索を用いて 9 を探索する過程を書きなさい。 (2) このデータから内挿探索を用いて 9 を探索する過程を書きなさい。 二分探索、内挿探索はソートされているデータに対して行う探索方法です。 二分探索（アルゴリズムＣ 第２巻 p.8） 真ん中のデータが見つけたいデータかどうか調べます。 見つけたいデータが真ん中のデータより小さければ左側に対して、 大きければ右側に対して、同じことを繰り返します。 内挿探索（アルゴリズムＣ 第２巻 p.1
Interpolation search - Wikipedia
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Interpolation search" – news · newspapers · books · scholar · JSTOR (September 2017) (Learn how and when to remove this message) Interpolation search is an algorithm for searching for a key in an array t
ラビン-カープ文字列検索アルゴリズム - Wikipedia
ラビン-カープ文字列検索アルゴリズム（英: Rabin-Karp string search algorithm）は、マイケル・ラビンとリチャード・カープが開発した、ハッシュ関数を利用してテキストからパターン（サブ文字列）を探す文字列検索アルゴリズムの一種[1][2]。1つのパターンの検索にはあまり用いられないが、理論的には重要であり、複数パターンの検索には効果的である。テキストの文字数が n、パターンの文字数が m とした場合、平均および最良の実行時間はO(n)だが、ごくまれに最悪性能として O(nm)となる（広く用いられないのはそのため）。しかし、k個の文字列のいずれかにマッチする部分を検索するのに要する時間は k によらず平均で O(n) となるという独特の利点を持つ。以下、単にラビン-カープまたはラビン-カープ法と略記することがある。 ラビン-カープの単純な応用例として、盗作の検出
DO++ : 最長一致文字列の話
たまには自分の研究紹介 D. Okanohara, K. Sadakane. "An Online Algorithm for Finding the Longest Previous Factors". In the 16th European Symposium on Algorithms. Sep 2008. to appear. [pdf(draft)] この研究では文字列を順々に読んでいったとき、各位置で過去に一番長くマッチした部分文字列を報告する問題を扱ってます。圧縮のLZ77法を知っているなら、マッチする部分を見つける部分を解いてます。で、圧縮以外にもいろいろなパターンマッチング問題とか、インデクシングとか、データマイニングとかいろいろなことにこの情報が利用できるということが知られてるみたいです。 で、大抵はハッシュやtrieを組んで履歴を探すんですが、今回対象にするのはテキ
高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」
はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは2003年に提案されたデータ構造、wavelet tree（以下「WT」と表記）です。WTは圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。WTは文字列T[0...n-1]が与えられた時、次の2つの操作を定数時間でサポートします。 rank(p, c)――T[0...p]中のcの出現回数を返す select(i, c)――(i+1)番目のcの位置を返す WTの作業領域量は、文字列をそのまま保存した時の約2倍程度です。 対象読者 C++の
Variable byte codes
Variable byte (VB) encoding uses an integral number of bytes to encode a gap. The last 7 bits of a byte are ``payload'' and encode part of the gap. The first bit of the byte is a continuation bit . It is set to 1 for the last byte of the encoded gap and to 0 otherwise. To decode a variable byte code, we read a sequence of bytes with continuation bit 0 terminated by a byte with continuation bit 1.
検索アルゴリズム (5)正規表現 -1-
検索アルゴリズム (5)正規表現 -1- 前回までは、固定文字列の照合アルゴリズムを紹介しましたが、この章では特定の「パターン」に合致する文字列を検索する処理、いわゆる「正規表現」(regular expression)を取り上げたいと思います。正規表現は、grep,sed,awk,perlなど、様々なツール、言語上でサポートされているので、たいていの方はその恩恵(?)に預かっているでしょう。 1)正規表現の定義 正規表現は、1つ以上の空白でない「枝」(branch)からなり、各「枝」は'|'で区切られます。正規表現は、「枝」の中のいずれかに一致した場合に「一致した」ことになるので、'|'は"論理和"の役割を持つといえます。
Introduction to Information Retrieval #2後半、#3前半 の復習資料 - naoyaのはてなダイアリー
Introduction to Information Retrieval 2章後半と3章前半の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_02_2.ppt http://bloghackers.net/~naoya/iir/ppt/iir_03_1.ppt 今回は 2 章の後半 postings list のマージの効率的な実装方法 フレーズインデックスと positional インデックスによるフレーズ検索の実現方法 3 章前半 辞書検索のためのデータ構造 ワイルドカードクエリの実現方法 という内容です。次回はスペルミス補正 (もしかして機能) についてになります。次回の輪読会は少し間が空いて 4/12 予定ですので復習資料のアップロードも 4 月になるかと思います。 過去の章のアーカイブは同 URL のデ
[を] 転置インデックスによる検索システムを作ってみよう！
転置インデックスによる検索システムを作ってみよう！ 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 ここ最近疲れ
![[を] 転置インデックスによる検索システムを作ってみよう！](https://cdn-ak-scissors.b.st-hatena.com/image/square/af37977ee866988286b95e74fff98500a190545c/height=288;version=1;width=512/https%3A%2F%2Fchalow.net%2Fimages%2Ftcl-logo-25.png){kind=logo}
横着プログラミング 第9回: sary: Suffix Array のライブラリとツール
最終更新日: 2002-12-18 (公開日: 2002-12-18) Unix Magazine 誌に 2002年1月号から 2003年2月号にかけて連載し ていた記事の元の原稿です。 私にフローチャートだけを見せて、テーブルは見せないとしたら、 私はずっと煙に巻かれたままになるだろう。逆にテーブルが見せて もらえるなら、フローチャートはたいてい必要なくなる。 -- Frederick P. Brooks Jr. *1 プログラミングにおいてはデータ構造が重要であり、正しいデータ 構造を選択すればアルゴリズムは自明なものとなる、という主張が ある。Rob Pike*2 の "Notes on Programming in C" *3 によると、現実的なプログラムに必要なデータ構造は次の 4つであ るという。 配列 (array) 連結リスト (linked list) ハッシュテーブル
suffix array
更新履歴 2004/01/07 O(N) 構築アルゴリズム三種追加（Ko &Alulu, Kim & al., Karkkainen & Sanders) Suffix Arrayは、最近注目を集めているデータ構造です。その理由として、 (1)大規模なデータに対して、高速に検索、情報抽出を行うことができる (2)BWTとしてデータ圧縮に用いることができる。 ことが挙げられます。(1)に関しては自然言語処理において、膨大な量のコーパスから情報（例えば、単語の出現回数など）を調べるときににSuffix Arrayを用いると非常に高速に求めることができます。 膨大な量のコーパスに基づいた自然言語処理が盛んになってきている今、Suffix Arrayが注目を集めています。 また、ゲノム情報を調べるバイオインフォマティクスにおいても、ここの配列と似ている部分（例えばCCAG）を調べるといった場合
B+ tree - Wikipedia
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article's use of external links may not follow Wikipedia's policies or guidelines. Please improve this article by removing excessive or inappropriate external links, and converting useful links where appropriate into footnote references. (October 201
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
cache:t-pdZ6N70goJ:qdbm.sourceforge.net/mikio/rbbs.cgi?id=RA11405505151800957518 byte aligned 符号 - Google 検索