もしかして機能はじめました 2007-12-18 - 新言語 Xtalを作る日記
LL魂のイベントで、Rubyにもしかして機能が追加された、というジョークを聞いて以来、そのうち実装してみたいなーと考えていました。 array.langwerth と length と書くつもりが手が滑ってlangwerthと書いてしまった場合、次のように表示されるようになりました。 lib::builtin::Array::langwerth は定義されていません。'length'と間違えている可能性があります。 あるクラスのメンバが無いとき、存在するメンバ名のedit distance*1が一番近いものを求めて表示します。 edit distanceは次のようにして求めています。 void edit_distance_helper(const void* data1, unsigned int size1, const void* data2, unsigned int size2,
スペル修正プログラムはどう書くか
Peter Norvig / 青木靖 訳 先週、2人の友人(ディーンとビル)がそれぞれ別個にGoogleが極めて早く正確にスペル修正できるのには驚くばかりだと私に言った。たとえば speling のような語でGoogleを検索すると、0.1秒くらいで答えが返ってきて、もしかして: spelling じゃないかと言ってくる(YahooやMicrosoftのものにも同様の機能がある)。ディーンとビルが高い実績を持ったエンジニアであり数学者であることを思えば、スペル修正のような統計的言語処理についてもっと知っていて良さそうなものなのにと私は驚いた。しかし彼らは知らなかった。よく考えてみれば、 別に彼らが知っているべき理由はないのだった。 間違っていたのは彼らの知識ではなく、私の仮定の方だ。 このことについてちゃんとした説明を書いておけば、彼らばかりでなく多くの人に有益かもしれない。Googleの
suffix array
更新履歴 2004/01/07 O(N) 構築アルゴリズム三種追加（Ko &Alulu, Kim & al., Karkkainen & Sanders) Suffix Arrayは、最近注目を集めているデータ構造です。その理由として、 (1)大規模なデータに対して、高速に検索、情報抽出を行うことができる (2)BWTとしてデータ圧縮に用いることができる。 ことが挙げられます。(1)に関しては自然言語処理において、膨大な量のコーパスから情報（例えば、単語の出現回数など）を調べるときににSuffix Arrayを用いると非常に高速に求めることができます。 膨大な量のコーパスに基づいた自然言語処理が盛んになってきている今、Suffix Arrayが注目を集めています。 また、ゲノム情報を調べるバイオインフォマティクスにおいても、ここの配列と似ている部分（例えばCCAG）を調べるといった場合
ボイヤー-ムーア文字列検索アルゴリズム - Wikipedia
一致サフィックス規則は概念上も実装上も不一致文字規則より格段に複雑である。ボイヤー-ムーア法が最後尾から照合を始めるのはこの規則のためである。形式的には次のように説明される[3]。 T に対して P がある位置に置かれ、T の部分文字列 t が P のサフィックスと一致しているが、その左隣の文字で不一致になったとする。そこで、t の左端からの部分文字列 t' が P のサフィックス以外の部分にないかを捜す。このとき、P のサフィックスの t の左隣の文字と P 内の t' の左隣の文字が違うものでなければならない。そして、P 内の部分文字列 t' が T の部分文字列 t と一致する位置に P をシフトする。t' が存在しなければ、P の左端が T における t の左端を過ぎた位置になるようシフトし、T 内の t のサフィックスとパターンのプレフィックスが一致するように配置する。そのような
クヌース–モリス–プラット法 - Wikipedia
クヌース–モリス–プラット法（Knuth–Morris–Pratt algorithm、KMP法と略記）とは、文字列検索アルゴリズムの一種。テキスト（文字列）Sから単語Wを探すにあたり、不一致となった位置と単語自身の情報から次に照合を試すべき位置を決定することで検索を効率化するアルゴリズムである。 このアルゴリズムは1977年、ドナルド・クヌースと Vaughan Pratt および（単独で）J. H. Morris が発明し、3人共同で発表した。 本項目では文字列を表すにあたって、0 からインデックスを開始する配列を用いる。従って（後述の）単語 W 内の文字 'C' は W[2] と表される。 KMP法[編集] この検索アルゴリズムの実施例[編集] 実際にこのアルゴリズムがどのように動作するかを見てみよう。このアルゴリズムの状態は二つの整数 m と i で表される。m はテキスト S 内
ソート・ルーチン (4)クイック・ソート
ソート・ルーチン (4)クイック・ソート 「速いソート・ルーチン」として今までシェル・ソートとヒープ・ソートを紹介してきましたが、今回は最後に残された「速いソート・ルーチン」として「クイック・ソート」を紹介します。クイック・ソートは、その名が示す通り現時点で最高速を誇るアルゴリズムであり、初期化の手間が要らず、細部の処理も簡潔であることからヒープ・ソートよりもさらに2倍は速くなるようです。 1)クイック・ソートのアルゴリズム クイック・ソート(Quick Sort)のアルゴリズムは、上にも書いたようにいたってシンプルです。 配列中の適当な要素を"境界値"として選び、仮にxとする。 xより小さい要素を配列の先頭方向に、xより大きい要素を配列の末尾方向に移動して、配列を2つの区間に分割する。 各区間に要素が1つしか含まれない状態になるまで、それぞれの分割した区間に対して1,2を繰り返す。全ての
検索アルゴリズム (4)文字列の検索 -2-
検索アルゴリズム (4)文字列の検索 -2- 前章に引き続き文字列照合(string matching)のアルゴリズムから、この章ではBoyer-Moore(BM)法を紹介したいと思います。このアルゴリズムは、実用上最速な文字列照合アルゴリズムとして文字列検索ツールやエディタで使用されているようです。 1)BM法 BoyerとMoore、また両者とは別にGosperが考案したBoyer-Moore(BM)法の最大の特徴は、パターンを末尾側から逆方向に比較するということです。 テキストとパターンの先頭をそろえた後、今までのアルゴリズムではパターン先頭とテキスト先頭を比較するのですが、BM法ではパターン末尾(先頭からm文字目)の文字と、テキストのm文字目の文字を比較します。もし一致していたら注目文字を1つ前にずらし、末尾側から逆方向に比較していきます。もし不一致が検出されたら、不一致を引き起
検索アルゴリズム (3)文字列の検索 -1-
テキストとパターンの中で、両側に下線が引かれた文字は一致したもの、パターンのみに下線が引かれた文字は不一致を検出した個所を示します。 それでは早速サンプルを示したいと思います。 int strlen( s ) char *s; { int i; for ( i = 0 ; s[i] != '\0' ; i++ ); return( i ); } int strncmp( s1, s2, len ) char *s1,*s2; int len; { int i; int cmpret = 0; for ( i = 0 ; i < len ; i++ ) if ( ( cmpret = s1[i] - s2[i] ) != 0 ) break; return( cmpret ); } char *strstr( Text, Pattern ) char *Text, *Pattern; { i
検索アルゴリズム (2)2分検索/木検索
検索アルゴリズム (2)2分検索/木検索 検索アルゴリズムの2回目は2分検索と木検索です。 1)2分検索 前回紹介した線形検索は、n個のデータ列に対して平均n/2回の比較操作が必要となるため、処理速度はnに比例していると言えます。これに対して、2分検索(Binary Search)ではn個のデータ列に対して最悪でもlog2n回の比較回数で済むので、線形検索に対してかなりの性能向上が期待できます。 ただし、2分検索を行うためにはデータ列がソートされている必要があり、その分線形検索に比べて前処理のための時間が必要となります。また、1回の比較処理にかかる時間も線形検索より長くなるため、データ数が少ない場合は2分検索の方がかえって遅くなることも考えられます。 2分検索では、まずデータ列の中央にある要素(以下mとします)と検索対象データ(以下xとします)を比較し、一致しなければxとmの大小関係より
検索アルゴリズム (1)線形探索/ハッシュ法
検索アルゴリズム (1)線形探索/ハッシュ法 今回からはまた、画像処理関係のアルゴリズムから離れて、探索・検索アルゴリズムの紹介を行いたいと思います。もう1つ候補として画像圧縮法があったのですが、こちらはかなりの分量になりそう&まだ文献などのチェックが終わってないので、先に軽めのやつから片付けてしまいます。 1)線形探索 あるデータ配列から特定の要素を検索する場合、まず誰でも思いつくのはデータの先頭から1つずつ要素を比較していくやり方だと思います(書類の山から目的のものを探すとき、一番上から順に見ていくのと同じですね)。この方法は線形探索(linear search)と呼ばれています。 アルゴリズムとしては非常に単純なものなので、早速サンプルを示したいと思います。 int *LinearSearch( DataStart, DataEnd, Data ) int *DataStart, *
高林 哲の「検索技術論」（上）：ITpro
フリー・ソフトウェアとして開発された全文検索システム「Namazu」は企業や官公庁を始め広く使われている。しかしその開発者である筆者は現在あまりNamazuを利用していない。彼自身の情報管理にはもっとシンプルな手法が適していると気づいたためだ。検索技術は適材適所が肝心である。 ローテク検索に至る顛末 数年前までよく耳にしたが，最近はあまり聞かれなくなった話題は多い。例えば「情報の氾濫が深刻化して必要な情報を見つけ出せなくなる」などというのもその一つだ。実際に情報の氾濫が収まってきたのか，単にニュースとして取り上げられなくなっただけなのかは分からない。ただインターネットにおける検索技術が，情報の急激な増加に追いつくべく格段に向上していることは確かである。 現在インターネット検索の代名詞になっている「Google」を提供する米Google社は，自社のミッションとして「世界中の情報を組織化し，世
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
