翻訳と辞書
Words near each other
・ エイベル・ガウワー
・ エイベル・タスマン国立公園
・ エイベル・パーカー・アップシャー
・ エイベン・カンデル
・ エイペック
・ エイペックス
・ エイペックス (中古半導体卸)
・ エイペックスタワー浦和
・ エイホ
・ エイホ (小惑星)
エイホ-コラシック法
・ エイホ–コラシック法
・ エイボン
・ エイボンの書
・ エイボンデール造船所
・ エイボン・プロダクツ
・ エイボン・プロダクツ株式会社
・ エイボン女性大賞
・ エイボン女性年度賞
・ エイボン川


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

エイホ-コラシック法 : ミニ英和和英辞書
エイホ-コラシック法[えいほこらしっくほう]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

: [ほう]
  1. (n,n-suf) Act (law: the X Act) 

エイホ-コラシック法 ( リダイレクト:エイホ–コラシック法 ) : ウィキペディア日本語版
エイホ–コラシック法[えいほこらしっくほう]
エイホ–コラシック法()とは、1975年にアルフレッド・エイホと Margaret J. Corasick が発見した文字列探索アルゴリズムである。
== 概要 ==
エイホ–コラシック法は、入力テキストについて有限の文字列群(辞書)の各要素を探す辞書式マッチングアルゴリズムの一種である。全パターンのマッチングを一斉に探索するため、そのアルゴリズムの計算量はパターン群の長さに対しても対象テキストの長さに対しても線形であり、さらに見つかったマッチングの数に対しても線形である。全てのマッチングを検出するため、パターン群にサブ文字列があれば、重複して検出される点に注意されたい(つまり、辞書が a, aa, aaa, aaaa で、入力テキストが aaaa の場合など)。
大まかに言えば、このアルゴリズムはトライ木を構築し、サフィックス木的に文字列(例えばabc)を表すノードからその最長サフィックス(接尾部、例えばbc)を表すノードがあればそれへリンクし、さもなくば c を表すノードがあればそれへリンクし、それもなければルートノードにリンクする。このような最長サフィックスへのリンクを全てのノードが持っているため、そのリンクリストを辿ることで全てのマッチングを列挙できる。実行時にはトライ木として働き、最長のマッチングを探すと共に、サフィックスのリンクリストを活用することで計算量を線形に抑えている。辞書にあるノードに到達すると、その単語とそこからリンクされている辞書に含まれるノードが、マッチングした位置と共に出力される。
(例えばコンピュータウイルスのデータベースのように)パターン辞書が更新されると、オフラインでオートマトンの構築がなされ、それを今後使用するよう格納する。この場合、実行時の計算量は入力の長さとマッチすべきエントリ数に対して線形である。
UNIXのコマンド fgrep は本来エイホ-コラシック法に基づいていた。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「エイホ–コラシック法」の詳細全文を読む




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.