ブラウザよりも高速アクセス！
12 関係: 力まかせ探索、ラビン-カープ文字列検索アルゴリズム、プリプロセッサ、ドナルド・クヌース、アルファベット (計算機科学)、アルゴリズム、エイホ–コラシック法、クヌース–モリス–プラット法、接尾辞木、検索、文字列、文字列探索。
力まかせ探索
力まかせ探索（ちからまかせたんさく、Brute-force search）またはしらみつぶし探索（Exhaustive search）は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。 バックトラッキングと混同されやすいが、バックトラッキングでは解候補の大部分を明示的に探索することなく捨てることができる。例えば、エイト・クイーンは、8個のクイーンをチェスボード上で互いに取り合えない状態で配置するものである。力まかせ探索では 64! / 56!.
新しい！!: ボイヤー-ムーア文字列検索アルゴリズムと力まかせ探索 · 続きを見る »
ラビン-カープ文字列検索アルゴリズム
ラビン-カープ文字列検索アルゴリズム（Rabin-Karp string search algorithm）は、マイケル・ラビンとリチャード・カープが開発した、ハッシュ関数を利用してテキストからパターン（サブ文字列）を探す文字列検索アルゴリズムの一種。1つのパターンの検索にはあまり用いられないが、理論的には重要であり、複数パターンの検索には効果的である。テキストの文字数が n、パターンの文字数が m とした場合、平均および最良の実行時間はO(n)だが、ごくまれに最悪性能として O(nm)となる（広く用いられないのはそのため）。しかし、k個の文字列のいずれかにマッチする部分を検索するのに要する時間は k によらず平均で O(n) となるという独特の利点を持つ。以下、単にラビン-カープまたはラビン-カープ法と略記することがある。 ラビン-カープの単純な応用例として、盗作の検出がある。例えば、学生が『白鯨』に関する英語の論文を書いたとしよう。賢い教授は『白鯨』に関する様々な資料を集め、それらの全文を自動的に抽出するものとする。そこで、ラビン-カープを使えば学生の論文の任意の文がそれら資料からの丸写しかどうかを判定できる。微妙な修正で盗作を判定できなくなるのを防ぐには、大文字・小文字の別を無視し、句読点を無視すればよい。この場合の検索文字列数 k は膨大なので、単一文字列検索アルゴリズムは非現実的である。.
新しい！!: ボイヤー-ムーア文字列検索アルゴリズムとラビン-カープ文字列検索アルゴリズム · 続きを見る »
プリプロセッサ
プリプロセッサ (preprocessor) とは、一般にある処理を行うソフトウェアに対して、データ入力やデータ整形などの準備的な処理を行うソフトウェアのことである。特にコンパイラに対して使うことが多く、ここではそれを中心に述べる。 他の分野の例としては、CADやCAEのデータ処理がある。またワープロソフトウェアにおける漢字変換ソフトウェアもプリプロセッサの一例である。.
新しい！!: ボイヤー-ムーア文字列検索アルゴリズムとプリプロセッサ · 続きを見る »
ドナルド・クヌース
ドナルド・エルビン・クヌース（Donald Ervin Knuth, 1938年1月10日 -）は数学者、計算機科学者。スタンフォード大学名誉教授。 クヌースによるアルゴリズムに関する著作 The Art of Computer Programming のシリーズはプログラミングに携わるものの間では有名である。アルゴリズム解析と呼ばれる分野を開拓し、計算理論の発展に多大な貢献をしている。その過程で漸近記法で計算量を表すことを一般化させた。 理論計算機科学への貢献とは別に、コンピュータによる組版システム TeX とフォント設計システム METAFONT の開発者でもあり、Computer Modern という書体ファミリも開発した。 作家であり学者であるクヌースは、文芸的プログラミングのコンセプトを生み出し、そのためのプログラミングシステム WEB / CWEB を開発。また、MIX / MMIX 命令セットアーキテクチャを設計。.
新しい！!: ボイヤー-ムーア文字列検索アルゴリズムとドナルド・クヌース · 続きを見る »
アルファベット (計算機科学)
形式言語とオートマトンの理論において、アルファベット (英: alphabet) または字母とは、文字や数字などといったような「記号」の有限の集合のこと。有限の文字列は、アルファベットからなる文字の有限の並びである。特に、からなるアルファベットはバイナリアルファベットと呼ばれる。また、二進列 (binary string)は、バイナリアルファベットの並びである。また、うまく処理することで、無限の文字の並びも考えることが可能である。 アルファベットΣが与えられたとき、Σ*はアルファベットΣからなる有限の文字列全てを意味する。ここでの*はクリーネ閉包を意味する演算子である。また、\Sigma^\infty (or occasionally, \Sigma^\N or \Sigma^\omega)は、アルファベットΣからなる無限の文字列全てを意味する。 例えばバイナリアルファベットからはのような文字列が生成できる（εは空文字列を意味する）。.
新しい！!: ボイヤー-ムーア文字列検索アルゴリズムとアルファベット (計算機科学) · 続きを見る »
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい！!: ボイヤー-ムーア文字列検索アルゴリズムとアルゴリズム · 続きを見る »
エイホ–コラシック法
イホ–コラシック法（Aho–Corasick algorithm）とは、1975年にアルフレッド・エイホと Margaret J. Corasick が発見した文字列探索アルゴリズムである。.
新しい！!: ボイヤー-ムーア文字列検索アルゴリズムとエイホ–コラシック法 · 続きを見る »
クヌース–モリス–プラット法
ヌース–モリス–プラット法（Knuth–Morris–Pratt algorithm、KMP法と略記）とは、文字列検索アルゴリズムの一種。テキスト（文字列）Sから単語Wを探すにあたり、不一致となった位置と単語自身の情報から次に照合を試すべき位置を決定することで検索を効率化するアルゴリズムである。 このアルゴリズムは1977年、ドナルド・クヌースと Vaughan Pratt および（単独で）J.
新しい！!: ボイヤー-ムーア文字列検索アルゴリズムとクヌース–モリス–プラット法 · 続きを見る »
接尾辞木
文字列 BANANA に $ を補った接尾辞木。根から葉（四角で表示）への6つの経路が6つの接尾辞 A$, NA$, ANA$, NANA$, ANANA$, BANANA$ に対応。四角の中の数字は対応する接尾辞の開始位置を示す。接尾辞リンクは破線の矢印で示されている。 接尾辞木（せつびじき）またはサフィックス木（Suffix tree）は、与えられた文字列の接尾部を木構造(基数木)で表すデータ構造であり、多くの文字列操作の高速な実装に利用されている。 文字列 S の接尾辞木は木構造であり、その枝には文字列が対応し、木構造の根から葉までの経路ごとにそれぞれ S の接尾部の1つが対応している。従って、これは S の接尾部に関する基数木である。 文字列 S からそのような木構造を構築するには、S の長さに対して線形な時間と空間を要する。構築できれば、いくつかの操作が高速化される（S の部分文字列を探す、誤字をある程度許容した上での部分文字列特定、正規表現パターンとのマッチングなど）。接尾辞木は最長共通部分文字列問題の線形な解法の1つでもある。これらの高速化の代償として、接尾辞木に要するメモリ空間は文字列そのものを格納するのに要するメモリ空間よりもかなり大きくなる。.
新しい！!: ボイヤー-ムーア文字列検索アルゴリズムと接尾辞木 · 続きを見る »
検索
検索（けんさく、search）とは、データの集合の中から目的とするデータを探し出すことである。古くは図書館の所蔵物を探し出したり、辞書の項目を引いたりといった人手で行うのが主だったが、コンピューターの発達により、テキスト文字列の検索（文書検索、文字列探索）、画像データの検索（画像検索）、音声データの検索（音声検索）など、大規模かつマルチメディアの情報に関する検索技術が発展した。さらにデータベースの発展とインターネットの普及に伴い、分散保管されているデータに対する検索技術が研究されている。ファイルの内容に対して文字列探索を行う機能も検索と呼ばれる。.
新しい！!: ボイヤー-ムーア文字列検索アルゴリズムと検索 · 続きを見る »
文字列
文字列（もじれつ）は、単語や文章のような、文字の連なったもの。ストリング (string)、テキスト (text) という場合もある。コンピュータ、特にプログラミングの分野で用いることが多い。.
新しい！!: ボイヤー-ムーア文字列検索アルゴリズムと文字列 · 続きを見る »
文字列探索
文字列探索 (もじれつたんさく) とは、ある文字列の中から、別のある文字列を探索することである。テキストエディタ等で必須の機能であり、これまでさまざまなアルゴリズムが考案されている。 ここでいう文字列とは、ある定まった文字集合の要素を任意に並べた系列のことである。通常、文字はアルファベット等の言語に依拠した文字セットを指すことが多いが、生物情報学における染色体の塩基配列A, T, G, Cの4文字を対象とするもののように、特定の領域に特化した応用も行われている。 正規表現にマッチする文字列の探索、と類似した問題だが、正規表現で可能なパターンに比べ検索対象を絞ることで、より高速に探索するものとして研究されている（ユーザの使うプログラムでは、検索するパターンに応じて、アルゴリズムを切り替えるものもある）。正規表現による探索については正規表現の記事を参照のこと。 近年は、暗号化された文字列を復号せずに探索する秘匿検索、圧縮テキスト中の文字列探索の研究、多国語文字列のバイト列表現に対する探索の研究、なども行われている。.
新しい！!: ボイヤー-ムーア文字列検索アルゴリズムと文字列探索 · 続きを見る »
