JPH0675992A - テキストをインデックス及び検索するための関連ワード形態の限定状態トランスジューサ - Google Patents
テキストをインデックス及び検索するための関連ワード形態の限定状態トランスジューサInfo
- Publication number
- JPH0675992A JPH0675992A JP5159804A JP15980493A JPH0675992A JP H0675992 A JPH0675992 A JP H0675992A JP 5159804 A JP5159804 A JP 5159804A JP 15980493 A JP15980493 A JP 15980493A JP H0675992 A JPH0675992 A JP H0675992A
- Authority
- JP
- Japan
- Prior art keywords
- fst
- word
- stem
- language
- branch
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/30—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
- G06F16/33—Querying
- G06F16/3331—Query processing
- G06F16/3332—Query translation
- G06F16/3338—Query expansion
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/30—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
- G06F16/31—Indexing; Data structures therefor; Storage structures
- G06F16/313—Selection or weighting of terms for indexing
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/30—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
- G06F16/33—Querying
- G06F16/3331—Query processing
- G06F16/3332—Query translation
- G06F16/3334—Selection or weighting of terms from queries, including natural language queries
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/30—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
- G06F16/33—Querying
- G06F16/3331—Query processing
- G06F16/3332—Query translation
- G06F16/3335—Syntactic pre-processing, e.g. stopword elimination, stemming
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/30—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
- G06F16/33—Querying
- G06F16/3331—Query processing
- G06F16/334—Query execution
- G06F16/3344—Query execution using natural language analysis
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/903—Querying
- G06F16/90335—Query processing
- G06F16/90344—Query processing by using string matching techniques
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/903—Querying
- G06F16/90335—Query processing
- G06F16/90348—Query processing by searching ordered data, e.g. alpha-numerically ordered data
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99931—Database or file accessing
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Databases & Information Systems (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Computational Linguistics (AREA)
- Artificial Intelligence (AREA)
- Software Systems (AREA)
- Machine Translation (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】
【目的】 中規模のデータベースにより、語幹決定を用
いてユーザの質問に対する応答性を著しく改善したコン
ピュータ化した情報検索システムを提供する。 【構成】 英語のような接尾語言語のみに限定されずに
世界中の言語に一般に適用できる情報検索システムであ
って、種々の構成の限定状態トランスジューサを使用
し、言語の形態学的ルールの系統的観点と、ワードごと
の不規則性とを考慮して、ワードとその語幹との間の前
後のマッピングを多数の種々の仕方で正確にエンコード
し、トランスジューサは、多数の状態及び遷移即ちアー
クを有することができるが、限定状態圧縮アルゴリズム
によってコンパクト化され、リソースに制約のある用途
にも使用でき、そして新規な限定状態トランスジューサ
をデータベースとして備えていると共に、ユーザの質問
に応答し、データベースをサーチし、適当な応答が存在
する場合にそれを出力するためのプロセッサとを備えた
情報検索システム。
いてユーザの質問に対する応答性を著しく改善したコン
ピュータ化した情報検索システムを提供する。 【構成】 英語のような接尾語言語のみに限定されずに
世界中の言語に一般に適用できる情報検索システムであ
って、種々の構成の限定状態トランスジューサを使用
し、言語の形態学的ルールの系統的観点と、ワードごと
の不規則性とを考慮して、ワードとその語幹との間の前
後のマッピングを多数の種々の仕方で正確にエンコード
し、トランスジューサは、多数の状態及び遷移即ちアー
クを有することができるが、限定状態圧縮アルゴリズム
によってコンパクト化され、リソースに制約のある用途
にも使用でき、そして新規な限定状態トランスジューサ
をデータベースとして備えていると共に、ユーザの質問
に応答し、データベースをサーチし、適当な応答が存在
する場合にそれを出力するためのプロセッサとを備えた
情報検索システム。
Description
【０００１】
【産業上の利用分野】本発明は、テキストをインデック
スし検索するコンピュータ化された情報検索装置又はシ
ステム、このような情報検索装置に使用するデータベー
ス、及びこのようなデータベースを形成する方法に係
る。
スし検索するコンピュータ化された情報検索装置又はシ
ステム、このような情報検索装置に使用するデータベー
ス、及びこのようなデータベースを形成する方法に係
る。
【０００２】
【従来の技術】あらゆる自然言語は、自由テキストの中
に異なった形で現れるワードによって系統的に表される
べき意味の共通要素を考慮している。例えば、英語で、
「到着する(arrive)」の共通の意味は、感染的変化「到
着した(arrived) 」、「到着する(arrives) 」、「到着
しつつある(arriving)」（並びに「到着する(arrive)」
それ自体）と、派生的変化「到着(arrival) 」とによっ
て伝えられる。このような全ての変化についての意味の
共通要素を示す基本的なワードをしばしば語幹と称し、
そして変化形態から語幹を決定する言語形態学的な分析
プロセスをしばしば語幹決定と称する。語幹からそのあ
らゆる変化形態へ別の仕方で至るプロセスをしばしば合
成又は発生と称する。
に異なった形で現れるワードによって系統的に表される
べき意味の共通要素を考慮している。例えば、英語で、
「到着する(arrive)」の共通の意味は、感染的変化「到
着した(arrived) 」、「到着する(arrives) 」、「到着
しつつある(arriving)」（並びに「到着する(arrive)」
それ自体）と、派生的変化「到着(arrival) 」とによっ
て伝えられる。このような全ての変化についての意味の
共通要素を示す基本的なワードをしばしば語幹と称し、
そして変化形態から語幹を決定する言語形態学的な分析
プロセスをしばしば語幹決定と称する。語幹からそのあ
らゆる変化形態へ別の仕方で至るプロセスをしばしば合
成又は発生と称する。
【０００３】語幹決定は、自然言語文書の全テキストイ
ンデックス及び検索において重要な役割を果たすことが
できる。文書からテキスト文節をそれらの意味に基づい
てインデックスし検索することに主たる関心のあるユー
ザは、共通語幹の変化を区別するのを望まないことがあ
る。従って、ユーザが「到着しつつある(arriving)」の
ワードで質問に入る場合に、「到着する(arrive)」、
「到着する(arrives) 」等のいずれかを含むテキスト文
節に一致するものとして処理することができる。これ
は、精度を犠牲にすることなく呼び戻しを改善する重要
な効果を果たす。
ンデックス及び検索において重要な役割を果たすことが
できる。文書からテキスト文節をそれらの意味に基づい
てインデックスし検索することに主たる関心のあるユー
ザは、共通語幹の変化を区別するのを望まないことがあ
る。従って、ユーザが「到着しつつある(arriving)」の
ワードで質問に入る場合に、「到着する(arrive)」、
「到着する(arrives) 」等のいずれかを含むテキスト文
節に一致するものとして処理することができる。これ
は、精度を犠牲にすることなく呼び戻しを改善する重要
な効果を果たす。
【０００４】しかしながら、テキストのインデックス及
び検索に関する語幹決定は、英語のような言語形態学的
に単純な言語でも実施がかなり困難であることが分かっ
ている。英語に関する従来の技術（例えば、１９６８年
３月のメカニカル・トランスレーション・アンド・コン
ピューテショナル・リングシテックス１１の第２２ない
し３１頁に掲載されたＪ．Ｂ．ルービンス著の「語幹決
定アルゴリズムの開発(Development of a Stemming Alg
orithm) 」; 及び１９８０年７月のプログラム１４の第
３号、第１３０ないし１３７頁に掲載されたＭ．Ｆ．ポ
ーター著の「サフィックスストリッピンのためのアルゴ
リズム(An Algorithm for Suffix Stripping) 」）は、
ワードを語幹のようなキャノン的形態にマップさせるた
めに「テイル−クロッピング（尻尾切り）」アルゴリズ
ムを使用している。従って、系統的に変化するサフィッ
クス（接尾部）文字を剥がして各ワードを全ての変化に
共通の最も長いプレフィックス（接頭部）へとマップす
るルール即ちアルゴリズムが書かれる。例えば、「到着
する(arrive)」の全ての形態は、文字列「arriv 」("e"
をもたない）へと剥される。というのは、これが全ての
形態に共通する最も長い接頭部だからである（即ち、"
e" は"arriving"にも"arraival"にも現れないから) 。
例外を取り扱う特殊な機構をもたないと、このようなや
り方は、「泳ぐ(swim)」の全ての形態を「sw」に変換し
てしまう。というのは、これが変化しない最も長い接頭
部だからである。
び検索に関する語幹決定は、英語のような言語形態学的
に単純な言語でも実施がかなり困難であることが分かっ
ている。英語に関する従来の技術（例えば、１９６８年
３月のメカニカル・トランスレーション・アンド・コン
ピューテショナル・リングシテックス１１の第２２ない
し３１頁に掲載されたＪ．Ｂ．ルービンス著の「語幹決
定アルゴリズムの開発(Development of a Stemming Alg
orithm) 」; 及び１９８０年７月のプログラム１４の第
３号、第１３０ないし１３７頁に掲載されたＭ．Ｆ．ポ
ーター著の「サフィックスストリッピンのためのアルゴ
リズム(An Algorithm for Suffix Stripping) 」）は、
ワードを語幹のようなキャノン的形態にマップさせるた
めに「テイル−クロッピング（尻尾切り）」アルゴリズ
ムを使用している。従って、系統的に変化するサフィッ
クス（接尾部）文字を剥がして各ワードを全ての変化に
共通の最も長いプレフィックス（接頭部）へとマップす
るルール即ちアルゴリズムが書かれる。例えば、「到着
する(arrive)」の全ての形態は、文字列「arriv 」("e"
をもたない）へと剥される。というのは、これが全ての
形態に共通する最も長い接頭部だからである（即ち、"
e" は"arriving"にも"arraival"にも現れないから) 。
例外を取り扱う特殊な機構をもたないと、このようなや
り方は、「泳ぐ(swim)」の全ての形態を「sw」に変換し
てしまう。というのは、これが変化しない最も長い接頭
部だからである。
【０００５】
【発明が解決しようとする課題】この従来の解決策には
多数の欠点がある。先ず、それにより得られる語幹の文
字列は、しばしば英語のワードにならない（sw,arriv)
。これらは、ユーザの質問が知覚し得る仕方で解読さ
れているかの確認を希望する純真なユーザに提示するこ
とができない。
多数の欠点がある。先ず、それにより得られる語幹の文
字列は、しばしば英語のワードにならない（sw,arriv)
。これらは、ユーザの質問が知覚し得る仕方で解読さ
れているかの確認を希望する純真なユーザに提示するこ
とができない。
【０００６】第２に、この解決策は、不規則な感染的及
び派生的変化を取り扱う特殊な機構を必要とする。通常
は、最も明らかで且つ共通のケース（例えば、聞く(hea
r)→聞いた(heard) 、良い(good)→より良い(better)）
に対して例外辞書が設けられるが、この辞書の入力数
は、通常、得られるデータ構造が大きくなり過ぎないよ
うに制限される。例外的な変化を完全に処理しないと、
精度が悪化し、ある研究者は精度を実質的に下げずに語
幹の決定で呼び戻しを顕著に改善できないと結論する点
に至っている。
び派生的変化を取り扱う特殊な機構を必要とする。通常
は、最も明らかで且つ共通のケース（例えば、聞く(hea
r)→聞いた(heard) 、良い(good)→より良い(better)）
に対して例外辞書が設けられるが、この辞書の入力数
は、通常、得られるデータ構造が大きくなり過ぎないよ
うに制限される。例外的な変化を完全に処理しないと、
精度が悪化し、ある研究者は精度を実質的に下げずに語
幹の決定で呼び戻しを顕著に改善できないと結論する点
に至っている。
【０００７】第３に、これは一方向の解決策である。即
ち、ワードから語幹へマッピングするには良いが、所与
の語幹から全ての変形形態を発生することはできない。
又、語幹決定のアルゴリズムを質問のみに適用するだけ
でなく、インデックスを構成するためのサーチの前又は
サーチ中のいずれかに文書のテキスト自体にも適用し
て、語幹の付いたテキストワードに対して質問−語幹を
一致できる場合には適当なサーチ特性を発揮する。従っ
て、この解決策は、インデックス動作のための文書のデ
ータベースを予め処理できるか（これは語幹決定に対し
て改良を行うときに再実行しなければならない）或いは
サーチ中の語幹決定について時間的なペナルティが禁じ
られない場合のみに用途が限定される。
ち、ワードから語幹へマッピングするには良いが、所与
の語幹から全ての変形形態を発生することはできない。
又、語幹決定のアルゴリズムを質問のみに適用するだけ
でなく、インデックスを構成するためのサーチの前又は
サーチ中のいずれかに文書のテキスト自体にも適用し
て、語幹の付いたテキストワードに対して質問−語幹を
一致できる場合には適当なサーチ特性を発揮する。従っ
て、この解決策は、インデックス動作のための文書のデ
ータベースを予め処理できるか（これは語幹決定に対し
て改良を行うときに再実行しなければならない）或いは
サーチ中の語幹決定について時間的なペナルティが禁じ
られない場合のみに用途が限定される。
【０００８】更に、この技術は、語学研究上一般的でな
い。各々の自然言語ごとに全く異なるアルゴリズムを書
かねばならず、接頭部及び挿入部のある言語の特性を取
り扱うためには、このようなアルゴリズムの一般的な技
法すら変更しなければならない。
い。各々の自然言語ごとに全く異なるアルゴリズムを書
かねばならず、接頭部及び挿入部のある言語の特性を取
り扱うためには、このようなアルゴリズムの一般的な技
法すら変更しなければならない。
【０００９】そこで、本発明の主たる目的は、上記した
形式のシステムで、上記欠点の１つ以上を克服するよう
なシステムを提供することである。
形式のシステムで、上記欠点の１つ以上を克服するよう
なシステムを提供することである。
【００１０】本発明の別の目的は、語幹決定を用いてテ
キストをインデックス及び検索できるだけでなく、語幹
決定を用いてユーザの質問に対する応答性を著しく高め
ることのできるシステムを提供することである。
キストをインデックス及び検索できるだけでなく、語幹
決定を用いてユーザの質問に対する応答性を著しく高め
ることのできるシステムを提供することである。
【００１１】本発明の更に別の目的は、中程度のサイズ
のデータベースで実施できて公知システムより短い応答
時間を与える上記形式のシステムを提供することであ
る。
のデータベースで実施できて公知システムより短い応答
時間を与える上記形式のシステムを提供することであ
る。
【００１２】本発明の更に別の目的は、他の形式の自動
テキスト処理に適用できるシステムを提供することであ
る。
テキスト処理に適用できるシステムを提供することであ
る。
【００１３】本発明の更に別の目的は、上記形式のシス
テムに使用する改良されたデータベースと、このような
データベースを構成する改良された方法とを提供するこ
とである。
テムに使用する改良されたデータベースと、このような
データベースを構成する改良された方法とを提供するこ
とである。
【００１４】
【課題を解決するための手段】本発明は、自然言語文書
の全テキスト検索に語幹（ワードの意味のキャノン的指
示体）を用いる際の多数の問題を解決し、従って、精度
を犠牲にすることなく呼び戻しを改善することができ
る。
の全テキスト検索に語幹（ワードの意味のキャノン的指
示体）を用いる際の多数の問題を解決し、従って、精度
を犠牲にすることなく呼び戻しを改善することができ
る。
【００１５】本発明の１つの特徴によれば、同じワード
の感染的形態、いゆる変化を、同じキャノン的辞書の形
態即ち語句表示にマップできることが分かった。これ
は、規則的な形態及び不規則な形態の両方に適用され
る。
の感染的形態、いゆる変化を、同じキャノン的辞書の形
態即ち語句表示にマップできることが分かった。これ
は、規則的な形態及び不規則な形態の両方に適用され
る。
【００１６】本発明のこの特徴によれば、限定状態トラ
ンスジューサ（ＦＳＴ）によってマッピングが得られ
る。意外なことに、所望のマッピングを与えると共に、
適度なサイズであって、且つ質問に対して適度な応答時
間を与える単一の合体式限定状態トランスジューサを構
成できることが分かった。意外な点は、それ自身の一連
の状態を各々有する何百又は何千もの小さなＦＳＴの組
み合わせを表すこの単一のＦＳＴは、実際的でないかさ
もなくば使用が不可能であるような巨大なサイズのＦＳ
Ｔになると予想されていたことである。
ンスジューサ（ＦＳＴ）によってマッピングが得られ
る。意外なことに、所望のマッピングを与えると共に、
適度なサイズであって、且つ質問に対して適度な応答時
間を与える単一の合体式限定状態トランスジューサを構
成できることが分かった。意外な点は、それ自身の一連
の状態を各々有する何百又は何千もの小さなＦＳＴの組
み合わせを表すこの単一のＦＳＴは、実際的でないかさ
もなくば使用が不可能であるような巨大なサイズのＦＳ
Ｔになると予想されていたことである。
【００１７】本発明の別の特徴によれば、中程度のサイ
ズの単一のＦＳＴは、言語の必要性を満たすために形成
される小さなＦＳＴの合成及び交差の組み合わせにより
得られる。
ズの単一のＦＳＴは、言語の必要性を満たすために形成
される小さなＦＳＴの合成及び交差の組み合わせにより
得られる。
【００１８】上記発見の結果、本発明の他の特徴を表す
多数の重要な効果が確保される。ここに述べる技術は、
世界中の言語に一般に適用でき、英語のような簡単な接
尾語言語のみに限定されるものではない。
多数の重要な効果が確保される。ここに述べる技術は、
世界中の言語に一般に適用でき、英語のような簡単な接
尾語言語のみに限定されるものではない。
【００１９】本発明による合体式ＦＳＴは、色々な種類
の言語に適用できる非常に融通性のあるシステムを構成
するように多数の異なる仕方で形成することができる。
例えば、既存のデータベースを再構成又は変更する必要
なく不規則な形態を含むことができる。
の言語に適用できる非常に融通性のあるシステムを構成
するように多数の異なる仕方で形成することができる。
例えば、既存のデータベースを再構成又は変更する必要
なく不規則な形態を含むことができる。
【００２０】本発明のシステムは、１つの動作モードに
限定されるものではない。所与のテキストワードから語
幹を計算できる一方、その所与のワードの語幹に対して
他の全ての変化形態を計算することもできる。これらの
変化を用いて質問を拡張し、適当な文書が見つかる確率
を高めることができる。
限定されるものではない。所与のテキストワードから語
幹を計算できる一方、その所与のワードの語幹に対して
他の全ての変化形態を計算することもできる。これらの
変化を用いて質問を拡張し、適当な文書が見つかる確率
を高めることができる。
【００２１】又、本発明の概念は、正規化ＦＳＴを語幹
決定ＦＳＴと合成して、テキスト中の一連の句読点付き
文字をそれに対応する一連の語幹にマップする単一のト
ランスジューサを構成するようにも適用できる。
決定ＦＳＴと合成して、テキスト中の一連の句読点付き
文字をそれに対応する一連の語幹にマップする単一のト
ランスジューサを構成するようにも適用できる。
【００２２】本発明の更に別の特徴によれば、ワードを
接辞及びスピーチ部分タグに関連させると共に語幹にも
関連させるように構成されたＦＳＴ、ここでは言語形態
学的分析器と称する、が提供される。１つの実施例にお
いては、ＦＳＴは、ルックアップ及びルックダウン動作
を行うことのできる文字ベースのトランスジューサであ
る。このような分析器は、テキストの検索に有用である
だけでなく、他の形式の自動テキスト処理分野にも有用
である。
接辞及びスピーチ部分タグに関連させると共に語幹にも
関連させるように構成されたＦＳＴ、ここでは言語形態
学的分析器と称する、が提供される。１つの実施例にお
いては、ＦＳＴは、ルックアップ及びルックダウン動作
を行うことのできる文字ベースのトランスジューサであ
る。このような分析器は、テキストの検索に有用である
だけでなく、他の形式の自動テキスト処理分野にも有用
である。
【００２３】本発明は、添付図面を参照した以下の詳細
な説明から理解されよう。これは、本発明の好ましい実
施例を一例として示すもので、本発明をこれに限定する
ものではない。
な説明から理解されよう。これは、本発明の好ましい実
施例を一例として示すもので、本発明をこれに限定する
ものではない。
【００２４】
【実施例】本発明の特徴は、系統的言語の考えられる全
ての語幹とその変化の関係を表すように限定状態トラン
スジューサより成る記憶されたデータベースを構成し、
そしてこれをテキストインデックス及び検索システムに
使用することである。より詳細には、本発明による限定
状態トランスジューサは、考えられる全てのテキスト形
態即ち表面形態の組を定め、そしてこの組をそれに対応
する語彙形態即ち語幹にマップすることである。
ての語幹とその変化の関係を表すように限定状態トラン
スジューサより成る記憶されたデータベースを構成し、
そしてこれをテキストインデックス及び検索システムに
使用することである。より詳細には、本発明による限定
状態トランスジューサは、考えられる全てのテキスト形
態即ち表面形態の組を定め、そしてこの組をそれに対応
する語彙形態即ち語幹にマップすることである。
【００２５】限定状態トランスジューサ（ＦＳＴ）は、
ストリングの順序付けされた対の組をエンコードするた
めの良く知られた装置である。例えば、１組の対｛＜ar
rivearrive ＞、＜arrive arriving ＞、＜arrive arri
ved＞、＜arrive arrives＞、＜arrive arrival＞｝
は、簡単なＦＳＴにおいてエンコードできる。一般に、
ＦＳＴは、「規則的な関係」を表すのに使用することが
でき、これは、この例のような順序付けされたストリン
グ対の限定リストを含むだけでなく、順序付けされた対
の幾種類かの限定収集体も含む。順序付けされた対がＦ
ＳＴのデータ構造体としていったんエンコードされる
と、この構造体をコンピュータプロセッサにより使用し
て、所与の入力に関連した全ての項目を得ることができ
る。従って、語幹「arrive」が与えられると、全ての種
々の形態を得ることができ（発生）、又は変化形態の１
つ(arrival) が与えられると、その語幹(arrive)を得る
ことができる。所与のワードが２つ以上の語幹の形態で
ある（例えば、「found 」は、「find」の過去形か又は
「found 」の現在形である）場合には、２つの正しい語
幹が与えられる。
ストリングの順序付けされた対の組をエンコードするた
めの良く知られた装置である。例えば、１組の対｛＜ar
rivearrive ＞、＜arrive arriving ＞、＜arrive arri
ved＞、＜arrive arrives＞、＜arrive arrival＞｝
は、簡単なＦＳＴにおいてエンコードできる。一般に、
ＦＳＴは、「規則的な関係」を表すのに使用することが
でき、これは、この例のような順序付けされたストリン
グ対の限定リストを含むだけでなく、順序付けされた対
の幾種類かの限定収集体も含む。順序付けされた対がＦ
ＳＴのデータ構造体としていったんエンコードされる
と、この構造体をコンピュータプロセッサにより使用し
て、所与の入力に関連した全ての項目を得ることができ
る。従って、語幹「arrive」が与えられると、全ての種
々の形態を得ることができ（発生）、又は変化形態の１
つ(arrival) が与えられると、その語幹(arrive)を得る
ことができる。所与のワードが２つ以上の語幹の形態で
ある（例えば、「found 」は、「find」の過去形か又は
「found 」の現在形である）場合には、２つの正しい語
幹が与えられる。
【００２６】図２は、２レベルのＦＳＴがいかに動作し
て感染型ワードをその語彙表示にマップするかを示して
いる。この場合は、語彙表示即ち語幹である「arrive」
を、表面レベルにおけるそのテキスト変化の１つである
「arriving」にマップする簡単なＦＳＴが示されてい
る。
て感染型ワードをその語彙表示にマップするかを示して
いる。この場合は、語彙表示即ち語幹である「arrive」
を、表面レベルにおけるそのテキスト変化の１つである
「arriving」にマップする簡単なＦＳＴが示されてい
る。
【００２７】次々の状態が円で表され、開始状態は
「ｓ」で示されそして終了状態は二重の円で示されてい
る。終了点の記号εは、匹敵する文字が存在しなくても
ＦＳＴがプロセスを続けられるようにするゼロ(NULL)記
号として働くイプシロンである。従って、図２に示す簡
単な状態の場合に、ユーザが「arrive」を入力すると、
ＦＳＴは、ルックダウン（即ち発生的）動作で「arrivi
ng」を出力する。又、ユーザが「arriving」を入力する
と、ＦＳＴは、ルックアップ（確認又は語幹決定）動作
で「arrive」を出力する。このように、下部の表面レベ
ルワードと上部の語彙表示との間でマップするように単
一のＦＳＴを容易に形成することができる。同様に、言
語ルールにより定められた変化への語幹のマッピングを
実行するように単一のＦＳＴを容易に形成することもで
きる。語彙表示は、スピーチの部分、大文字小文字の
別、性、数及び変化形態の他の言語形態学的特性に関す
る情報を含むことができる。この情報は、通常の文字と
同様にトランスジューサにおいてアークラベルを形成す
る記号タグの形態の語彙表示でエンコードすることがで
きる。例えば、図２に示すように、「arriving」という
形態を語幹「arrive」のみにマップするのではなく、+P
resPart という形態学的タグで表示されたアークをトラ
ンスジューサに追加して、「arriving」は「arrive」の
現在分詞形であるという情報をエンコードすることがで
きる。これが図１９に示されている。ワードを接辞及び
スピーチ部分タグ並びに語幹に関連付けるよう構成され
たトランスジューサを「言語形態学的分析トランスジュ
ーサ」又は「言語形態学的分析器」と称する。これらの
トランスジューサは、上部側のストリングに余計なタグ
情報が含まれたという点のみが通常の語幹決定トランス
ジューサとは異なり、これらは全く同じ技術及びアルゴ
リズムにより構成、操作、圧縮及び適用することができ
る。
「ｓ」で示されそして終了状態は二重の円で示されてい
る。終了点の記号εは、匹敵する文字が存在しなくても
ＦＳＴがプロセスを続けられるようにするゼロ(NULL)記
号として働くイプシロンである。従って、図２に示す簡
単な状態の場合に、ユーザが「arrive」を入力すると、
ＦＳＴは、ルックダウン（即ち発生的）動作で「arrivi
ng」を出力する。又、ユーザが「arriving」を入力する
と、ＦＳＴは、ルックアップ（確認又は語幹決定）動作
で「arrive」を出力する。このように、下部の表面レベ
ルワードと上部の語彙表示との間でマップするように単
一のＦＳＴを容易に形成することができる。同様に、言
語ルールにより定められた変化への語幹のマッピングを
実行するように単一のＦＳＴを容易に形成することもで
きる。語彙表示は、スピーチの部分、大文字小文字の
別、性、数及び変化形態の他の言語形態学的特性に関す
る情報を含むことができる。この情報は、通常の文字と
同様にトランスジューサにおいてアークラベルを形成す
る記号タグの形態の語彙表示でエンコードすることがで
きる。例えば、図２に示すように、「arriving」という
形態を語幹「arrive」のみにマップするのではなく、+P
resPart という形態学的タグで表示されたアークをトラ
ンスジューサに追加して、「arriving」は「arrive」の
現在分詞形であるという情報をエンコードすることがで
きる。これが図１９に示されている。ワードを接辞及び
スピーチ部分タグ並びに語幹に関連付けるよう構成され
たトランスジューサを「言語形態学的分析トランスジュ
ーサ」又は「言語形態学的分析器」と称する。これらの
トランスジューサは、上部側のストリングに余計なタグ
情報が含まれたという点のみが通常の語幹決定トランス
ジューサとは異なり、これらは全く同じ技術及びアルゴ
リズムにより構成、操作、圧縮及び適用することができ
る。
【００２８】図１９のトランスジューサは、下向きの矢
印で表された発生（ルックダウン）モードで使用され
て、適当な形態「arriving」を導出すると共に、上向き
の矢印で表された確認（ルックアップ）モードで使用さ
れて、ワード「arriving」を、語幹「arrive」及び接尾
部「ing 」で表される形態学的特徴にマップすることが
できる。図１９に示したアルファベットの形態学的タグ
を含む文字ベースのトランスジューサは、公知のトラン
スジューサよりも形態学的分析及び発生について非常に
コンパクトなツールである。公知のトランスジューサは
文字ではなくテストリングをアークラベルとして使用す
る。これは、文字ベースのトランスジューサに比してア
ルファベットのサイズを著しく増加し、対応するルック
アップ及びルックダウン動作において非常に複雑な一致
を必要とする。更に、文字ラベルの付いた遷移を用いる
本発明の技術では、標準的な決定及び最小化アルゴリズ
ムにより、言語の多数のワードが分担する最初と終わり
のサブストリングをつぶすことができる。この作用が図
２０及び２１に示されており、少数のワード（arrivin
g, arresting, arrogating ）に対し、本発明の文字ベ
ースの表示で許される最初のサブストリングの分担（図
２０）と、それに対応するストリングベースの表示（図
２１）とが対比されている。図２０と２１とで、文字ａ
及びｒの発生がどれほど少ないかに注目されたい。文字
ベースの分担は、全言語トランスジューサのサイズを著
しく減少することができる。両形式のトランスジューサ
は、形態学的情報を実際に状態についての注釈として表
しアークラベルとしては表さない形式のシステムよりは
分析についてより効率的である。
印で表された発生（ルックダウン）モードで使用され
て、適当な形態「arriving」を導出すると共に、上向き
の矢印で表された確認（ルックアップ）モードで使用さ
れて、ワード「arriving」を、語幹「arrive」及び接尾
部「ing 」で表される形態学的特徴にマップすることが
できる。図１９に示したアルファベットの形態学的タグ
を含む文字ベースのトランスジューサは、公知のトラン
スジューサよりも形態学的分析及び発生について非常に
コンパクトなツールである。公知のトランスジューサは
文字ではなくテストリングをアークラベルとして使用す
る。これは、文字ベースのトランスジューサに比してア
ルファベットのサイズを著しく増加し、対応するルック
アップ及びルックダウン動作において非常に複雑な一致
を必要とする。更に、文字ラベルの付いた遷移を用いる
本発明の技術では、標準的な決定及び最小化アルゴリズ
ムにより、言語の多数のワードが分担する最初と終わり
のサブストリングをつぶすことができる。この作用が図
２０及び２１に示されており、少数のワード（arrivin
g, arresting, arrogating ）に対し、本発明の文字ベ
ースの表示で許される最初のサブストリングの分担（図
２０）と、それに対応するストリングベースの表示（図
２１）とが対比されている。図２０と２１とで、文字ａ
及びｒの発生がどれほど少ないかに注目されたい。文字
ベースの分担は、全言語トランスジューサのサイズを著
しく減少することができる。両形式のトランスジューサ
は、形態学的情報を実際に状態についての注釈として表
しアークラベルとしては表さない形式のシステムよりは
分析についてより効率的である。
【００２９】形態学的分析トランスジューサは、テキス
トの検索を行うのに有用であるだけでなく、他の形式の
自動テキスト処理分野にも有用である。例えば、人々が
参考として使用することのある動詞の連結及び切断を行
ったり、特に英語以上に浸透する言語を教えたりするた
めの装置に使用することができる。これらは、最初のル
ックアップ段階において、機械で別の目標言語に変換す
べきソース言語入力センテンスのワードを処理し、そし
て最後のルックダウン段階において、その変換プロセス
により得られた形態学的特性から目標言語の実際のワー
ドを形成するように使用できる。別の例としては、自然
言語のセンテンスをデータベース質問システムにおいて
分解する前にルックアップ段階で使用することもでき
る。
トの検索を行うのに有用であるだけでなく、他の形式の
自動テキスト処理分野にも有用である。例えば、人々が
参考として使用することのある動詞の連結及び切断を行
ったり、特に英語以上に浸透する言語を教えたりするた
めの装置に使用することができる。これらは、最初のル
ックアップ段階において、機械で別の目標言語に変換す
べきソース言語入力センテンスのワードを処理し、そし
て最後のルックダウン段階において、その変換プロセス
により得られた形態学的特性から目標言語の実際のワー
ドを形成するように使用できる。別の例としては、自然
言語のセンテンスをデータベース質問システムにおいて
分解する前にルックアップ段階で使用することもでき
る。
【００３０】言語のワードは多数の異なる方法で定める
ことができる。例えば、言語を表す語彙集は、次のもの
を含むことができる。
ことができる。例えば、言語を表す語彙集は、次のもの
を含むことができる。
【００３１】１．限定された数の語幹／変化対しか言語
にない場合には、これらを簡単にリストすることができ
る（図３）。このリストは、規則的及び不規則な語幹／
変化対を含む（図４）。２．系統的な伝染的及び派生的
代替物、例えば、語幹の規則的ワード変化は、言語学ル
ールシステム即ち文法によって表すことができ、多数の
種類のルール（例えば、２レベルのルール及び順序付け
された再書き込みシステム）をＦＳＴコンパイル機能に
組み込むのが好ましい（図５）。３．上記２項のルール
システムを、限定リスト（図６）として簡単にリストで
きる未解決の不規則な形態と組み合わせる。
にない場合には、これらを簡単にリストすることができ
る（図３）。このリストは、規則的及び不規則な語幹／
変化対を含む（図４）。２．系統的な伝染的及び派生的
代替物、例えば、語幹の規則的ワード変化は、言語学ル
ールシステム即ち文法によって表すことができ、多数の
種類のルール（例えば、２レベルのルール及び順序付け
された再書き込みシステム）をＦＳＴコンパイル機能に
組み込むのが好ましい（図５）。３．上記２項のルール
システムを、限定リスト（図６）として簡単にリストで
きる未解決の不規則な形態と組み合わせる。
【００３２】従って、これにより得られる言語を表す語
彙集は、各リストエレメント又はルールのマッピングを
行うようにＦＳＴを形成して、リストで作り上げられる
か、ルールで作り上げられるか、或いはリスト及びルー
ルで作り上げられる。これらの全てを１つのグループと
して適切に解釈するシステムに匹敵するにはこのような
ＦＳＴが数百あり、そしてこのシステムを正しく且つ効
率的に実施することは困難である。しかしながら、これ
らは全て、その全部が一緒に動作するのと同じ作用をも
つ単一のＦＳＴに合体することができ、単一のトランス
ジューサで発生及び確認を行うアルゴリズムは、簡単で
且つ効率的である。これが図７に示されている。
彙集は、各リストエレメント又はルールのマッピングを
行うようにＦＳＴを形成して、リストで作り上げられる
か、ルールで作り上げられるか、或いはリスト及びルー
ルで作り上げられる。これらの全てを１つのグループと
して適切に解釈するシステムに匹敵するにはこのような
ＦＳＴが数百あり、そしてこのシステムを正しく且つ効
率的に実施することは困難である。しかしながら、これ
らは全て、その全部が一緒に動作するのと同じ作用をも
つ単一のＦＳＴに合体することができ、単一のトランス
ジューサで発生及び確認を行うアルゴリズムは、簡単で
且つ効率的である。これが図７に示されている。
【００３３】個々のＦＳＴは、主に２つの方法で合成さ
れる。図７の左側には、一連のＦＳＴ１０、１１、１
２、１３が直列関係で配列されており、その各々は文法
の特定のルール１、２、３．．．Ｎを実行する。これら
は、ＦＳＴの公知の合成アルゴリズムによりカスケード
状に合成されて単一のＦＳＴ１５に合体される。或いは
又、その右側に示したように、ルール１、２、３．．．
Ｎに対する個々のＦＳＴ１０’、１１’、１２’、１
３’を並列関係に配列し、公知の交差アルゴリズムによ
って単一の合体したＦＳＴ１５に合成することもでき
る。ＦＳＴがいかに形成されようと、ＦＳＴの計算法に
よりトランスジューサが合体されることが利点である。
特に、不規則な形態の限定リストに対応するトランスジ
ューサは、ルール（図６の組み合わせ）に対応するＦＳ
Ｔと次の方法で合体することができる。不規則な対（例
えば、＜hear heard＞）限定リストから導出されたトラ
ンスジューサをＩとしそして規則的なルール（誤って＜
hear heard＞を含む）から導出されたトランスジューサ
をＲとすれば、２つの情報源を適切に合体することがで
きる。好ましい方法は次の通りである。関係Ｉのドメイ
ンの補数に対する同一トランスジューサを計算し、これ
とＲを予め合成し、次いで、その結果をＩと結合する。
これにより、Ｉの例外によって拒絶されない場合だけＲ
に定められた語幹−変化のマッピングが与えられる。一
般に、最終的なＦＳＴは、多数の異なる技術によって定
められた部片から形成され、規則性を保持する非常に多
数の関連動作を用いて一緒に合成することができる。
れる。図７の左側には、一連のＦＳＴ１０、１１、１
２、１３が直列関係で配列されており、その各々は文法
の特定のルール１、２、３．．．Ｎを実行する。これら
は、ＦＳＴの公知の合成アルゴリズムによりカスケード
状に合成されて単一のＦＳＴ１５に合体される。或いは
又、その右側に示したように、ルール１、２、３．．．
Ｎに対する個々のＦＳＴ１０’、１１’、１２’、１
３’を並列関係に配列し、公知の交差アルゴリズムによ
って単一の合体したＦＳＴ１５に合成することもでき
る。ＦＳＴがいかに形成されようと、ＦＳＴの計算法に
よりトランスジューサが合体されることが利点である。
特に、不規則な形態の限定リストに対応するトランスジ
ューサは、ルール（図６の組み合わせ）に対応するＦＳ
Ｔと次の方法で合体することができる。不規則な対（例
えば、＜hear heard＞）限定リストから導出されたトラ
ンスジューサをＩとしそして規則的なルール（誤って＜
hear heard＞を含む）から導出されたトランスジューサ
をＲとすれば、２つの情報源を適切に合体することがで
きる。好ましい方法は次の通りである。関係Ｉのドメイ
ンの補数に対する同一トランスジューサを計算し、これ
とＲを予め合成し、次いで、その結果をＩと結合する。
これにより、Ｉの例外によって拒絶されない場合だけＲ
に定められた語幹−変化のマッピングが与えられる。一
般に、最終的なＦＳＴは、多数の異なる技術によって定
められた部片から形成され、規則性を保持する非常に多
数の関連動作を用いて一緒に合成することができる。
【００３４】語幹／変化の関係をエンコードするＦＳＴ
が形成されると、公知の尻尾切りアルゴリズムを使用す
るときにこのＦＳＴを直接使用して、一致の前に質問及
びテキストワードの両方の語幹を決定することができ
る。しかし、質問の変化形態を同じ語幹の他の全ての変
化の分離へと拡張する発生体として、これを逆の方法で
使用することもできる。従って、「arrive」を含む質問
は、可能性｛arrive, arrival, arrives, arrived, arr
iving ｝の分離へと拡張され、この１組の語を語幹決定
されないテキストに一致させることができる。語幹決定
トランスジューサをその逆構成と合成するだけでこの機
能を正確に発揮する単一のＦＳＴを容易に構成すること
ができる。ＦＳＴの逆構成は、各遷移ラベルの上部及び
下部記号を単に交換する公知の技術によって形成でき
る。これに対し、尻尾切りアルゴリズムの逆構成を計算
することは非常に困難であるか又は不可能である。
が形成されると、公知の尻尾切りアルゴリズムを使用す
るときにこのＦＳＴを直接使用して、一致の前に質問及
びテキストワードの両方の語幹を決定することができ
る。しかし、質問の変化形態を同じ語幹の他の全ての変
化の分離へと拡張する発生体として、これを逆の方法で
使用することもできる。従って、「arrive」を含む質問
は、可能性｛arrive, arrival, arrives, arrived, arr
iving ｝の分離へと拡張され、この１組の語を語幹決定
されないテキストに一致させることができる。語幹決定
トランスジューサをその逆構成と合成するだけでこの機
能を正確に発揮する単一のＦＳＴを容易に構成すること
ができる。ＦＳＴの逆構成は、各遷移ラベルの上部及び
下部記号を単に交換する公知の技術によって形成でき
る。これに対し、尻尾切りアルゴリズムの逆構成を計算
することは非常に困難であるか又は不可能である。
【００３５】上記の説明から明らかなように、例えば、
５６，０００の語幹と２１８，０００の変化を含む英語
のデータベースの場合に、得られるＦＳＴは巨大なサイ
ズとなって膨大な量の記憶メモリを必要とすると共に高
速アクセスのプロセッサでもかなりの時間を必要とする
ことが予想される。これは、より限定されたＣＰＵとメ
モリリソースを有するＰＣを使用しているユーザのメイ
ンフレームにとってもその重要な区分にとっても問題で
ある。本発明の更に別の特徴によれば、限定されたＲＡ
Ｍをもつ中程度の価格のＰＣでもこのようなＦＳＴを情
報検索語幹決定に対して実用的なものにする多数の技術
が開示される。これらの技術は、次のものを含む。
５６，０００の語幹と２１８，０００の変化を含む英語
のデータベースの場合に、得られるＦＳＴは巨大なサイ
ズとなって膨大な量の記憶メモリを必要とすると共に高
速アクセスのプロセッサでもかなりの時間を必要とする
ことが予想される。これは、より限定されたＣＰＵとメ
モリリソースを有するＰＣを使用しているユーザのメイ
ンフレームにとってもその重要な区分にとっても問題で
ある。本発明の更に別の特徴によれば、限定されたＲＡ
Ｍをもつ中程度の価格のＰＣでもこのようなＦＳＴを情
報検索語幹決定に対して実用的なものにする多数の技術
が開示される。これらの技術は、次のものを含む。
【００３６】（１）ワードリストを（１テープの）限定
状態マシン（ＦＳＭ）にコンパイルしそして語幹−変化
対及びルールを限定状態トランスジューサにコンパイル
する方法；（２）同じ入力−出力特性を有する単一のＦ
ＳＴを他のＦＳＴの全集合体として形成する方法；
（３）ＦＳＭデータ構造体においてＦＳＴを表す方法；
そして（４）ＦＳＭを最小空間においてエンコードする
技術。
状態マシン（ＦＳＭ）にコンパイルしそして語幹−変化
対及びルールを限定状態トランスジューサにコンパイル
する方法；（２）同じ入力−出力特性を有する単一のＦ
ＳＴを他のＦＳＴの全集合体として形成する方法；
（３）ＦＳＭデータ構造体においてＦＳＴを表す方法；
そして（４）ＦＳＭを最小空間においてエンコードする
技術。
【００３７】１つ以上の上記概念を組み込んで、単一の
ＦＳＴを形成しそしてこれを単純なＦＳＭ（感染形態又
は語彙形態のみを含んでいて、２つの表示間のマッピン
グはもたない）より適度に大きいサイズのみに圧縮する
ことが望ましい。
ＦＳＴを形成しそしてこれを単純なＦＳＭ（感染形態又
は語彙形態のみを含んでいて、２つの表示間のマッピン
グはもたない）より適度に大きいサイズのみに圧縮する
ことが望ましい。
【００３８】ＦＳＭデータ構造体をよりコンパクトな記
憶装置に対してエンコードする種々の技術が別の関連特
許出願に述べられている。これらの技術は、ＦＳＭデー
タ構造体の情報を、状態自体ではなくて状態間の遷移に
結び付けることに基づいている。１テープＦＳＭにおい
ては、遷移が単一文字で表示されるが、ＦＳＴでは、遷
移が文字対で表示される。図１８に示す非常に簡単な変
換によりＦＳＴをＦＳＭに変換することができる。各々
のＦＳＴ遷移は、一連の２つの遷移をもつ形式Ｘ：Ｙの
対ラベルと置き換えられ、Ｘと表示された方は、Ｘ：Ｙ
遷移の元の状態（「１」と示す）から離れて新たな状態
（「ＮＥＷ」と示す）へ通じており、そしてＹと表示さ
れた方は、この新たな状態からＸ：Ｙ遷移の行き先状態
（「２」と示す）へと通じている。このように全てのア
ークを置き換えた結果が、元のＦＳＴ遷移の上側及び下
側が各々奇数及び偶数遷移で表された１テープＦＳＭで
ある。このＦＳＭは、次いで、標準技術により決定され
そして最小にされる。従って、本発明のＦＳＴはそれに
等価なＦＳＭに変換することができ、上記関連出願のコ
ンパクト化技術及びアルゴリズムをこれに適用すること
ができる。これは、本発明の解決策の重要な利点であ
る。又、上記関連出願の計算マシンは、本発明を実施す
るのに使用できるマシンと同じ種類のものであることに
注意されたい。これらマシンについてはここでは詳細に
述べない。しかし、図１に示すように、マシン３０は単
純な汎用コンピュータであって、エンコードされたデー
タ構造体及びプログラムを通常の仕方で記憶する手段３
１（ＲＡＭ、ＲＯＭ、ＤＩＳＣ、又はテープ）を備えて
おり、このデータ構造体及びプログラムは、ＣＰＵ３２
で実行されると、ユーザの質問３３を受け取り、エンコ
ードされたメモリをサーチして（３４）、ユーザが供給
した入力との一致を探し、そして例えば、モニタ３６を
介してユーザに、その見つかった一致項目を出力する
か、それらが見つかった文書の識別を出力するか、又は
一致が見つからない指示を出力する、ということだけ述
べれば充分であろう。
憶装置に対してエンコードする種々の技術が別の関連特
許出願に述べられている。これらの技術は、ＦＳＭデー
タ構造体の情報を、状態自体ではなくて状態間の遷移に
結び付けることに基づいている。１テープＦＳＭにおい
ては、遷移が単一文字で表示されるが、ＦＳＴでは、遷
移が文字対で表示される。図１８に示す非常に簡単な変
換によりＦＳＴをＦＳＭに変換することができる。各々
のＦＳＴ遷移は、一連の２つの遷移をもつ形式Ｘ：Ｙの
対ラベルと置き換えられ、Ｘと表示された方は、Ｘ：Ｙ
遷移の元の状態（「１」と示す）から離れて新たな状態
（「ＮＥＷ」と示す）へ通じており、そしてＹと表示さ
れた方は、この新たな状態からＸ：Ｙ遷移の行き先状態
（「２」と示す）へと通じている。このように全てのア
ークを置き換えた結果が、元のＦＳＴ遷移の上側及び下
側が各々奇数及び偶数遷移で表された１テープＦＳＭで
ある。このＦＳＭは、次いで、標準技術により決定され
そして最小にされる。従って、本発明のＦＳＴはそれに
等価なＦＳＭに変換することができ、上記関連出願のコ
ンパクト化技術及びアルゴリズムをこれに適用すること
ができる。これは、本発明の解決策の重要な利点であ
る。又、上記関連出願の計算マシンは、本発明を実施す
るのに使用できるマシンと同じ種類のものであることに
注意されたい。これらマシンについてはここでは詳細に
述べない。しかし、図１に示すように、マシン３０は単
純な汎用コンピュータであって、エンコードされたデー
タ構造体及びプログラムを通常の仕方で記憶する手段３
１（ＲＡＭ、ＲＯＭ、ＤＩＳＣ、又はテープ）を備えて
おり、このデータ構造体及びプログラムは、ＣＰＵ３２
で実行されると、ユーザの質問３３を受け取り、エンコ
ードされたメモリをサーチして（３４）、ユーザが供給
した入力との一致を探し、そして例えば、モニタ３６を
介してユーザに、その見つかった一致項目を出力する
か、それらが見つかった文書の識別を出力するか、又は
一致が見つからない指示を出力する、ということだけ述
べれば充分であろう。
【００３９】図８は、ルールに基づく表面形態から語幹
又は語彙形態を発生するように形成されたＦＳＴの例を
示している。ワードの２レベルルールの例としては、語
彙Ｎが表面ｍとして現れるというもので、但し、これは
その後に語彙側にｐを伴う場合だけである（このｐ自身
がいかに現れるかに係わりなく）。この２レベルルール
は、式としては、Ｎ：ｍ＜＝＞ ｐである。このルール
は、ワード「impractical 」及び「intractable 」が各
々語彙形態「iNpractical 」及び「iNtractable 」から
導出されたもので、これらは「not 」の意味の接頭部と
して同じ語彙表示（ｉＮ）を有している。図８に示す対
応するトランスジューサは、状態５０、即ち開始及び終
了状態の両方である二重円を備えている。Ｎがｍとして
現れる場合には、トランスジューサは、状態５１、即ち
次の入力としてｐを必要とする非最終状態へ移動する。
Ｎがｎとして現れる場合には、トランスジューサは、ｐ
の追従を許さない状態５２へ移動する。従って、トラン
スジューサは、ルールでは明確に表されないという１つ
の追加事実をエンコードし、語彙Ｎは他の全ての場合に
ｎとして現れる。各ルールは、それら自身のＦＳＴを図
７について述べたように単一のルールＦＳＴに合成す
る。
又は語彙形態を発生するように形成されたＦＳＴの例を
示している。ワードの２レベルルールの例としては、語
彙Ｎが表面ｍとして現れるというもので、但し、これは
その後に語彙側にｐを伴う場合だけである（このｐ自身
がいかに現れるかに係わりなく）。この２レベルルール
は、式としては、Ｎ：ｍ＜＝＞ ｐである。このルール
は、ワード「impractical 」及び「intractable 」が各
々語彙形態「iNpractical 」及び「iNtractable 」から
導出されたもので、これらは「not 」の意味の接頭部と
して同じ語彙表示（ｉＮ）を有している。図８に示す対
応するトランスジューサは、状態５０、即ち開始及び終
了状態の両方である二重円を備えている。Ｎがｍとして
現れる場合には、トランスジューサは、状態５１、即ち
次の入力としてｐを必要とする非最終状態へ移動する。
Ｎがｎとして現れる場合には、トランスジューサは、ｐ
の追従を許さない状態５２へ移動する。従って、トラン
スジューサは、ルールでは明確に表されないという１つ
の追加事実をエンコードし、語彙Ｎは他の全ての場合に
ｎとして現れる。各ルールは、それら自身のＦＳＴを図
７について述べたように単一のルールＦＳＴに合成す
る。
【００４０】ＦＳＭ及びＦＳＴを含む限定自動機械の状
態を最小にするためのアルゴリズムとしては多数のもの
が知られていることを理解されたい。得られるデータ構
造体のサイズを更に減少するためにもこれらを使用しな
ければならない。
態を最小にするためのアルゴリズムとしては多数のもの
が知られていることを理解されたい。得られるデータ構
造体のサイズを更に減少するためにもこれらを使用しな
ければならない。
【００４１】言語のアルファベットの全てのストリング
が真の語幹であるかどうかに係わりなく又そうであった
としても、これら全てのストリングに文法の１組のルー
ルが適用される。これらルールは、特定の辞書もしくは
語彙集にリストされた項目のみに適用するように制約す
るのが望ましい。語彙集におけるワードのリストは、限
定状態マシンとして表すことができるので、この制約
は、ＦＳＴ合成演算子によって達成することができる。
語彙集の各ワードをそれ自身へとマップする同一トラン
スジューサが形成されるが、これは、例えば、ＦＳＭに
おける各遷移のラベルを、そのラベルの２つの場合を含
む対と置き換えることによって行うことができる。この
同一トランスジューサは、ルール及び不規則形態（図
６）を表すＦＳＴと合成される。これにより得たＦＳＴ
は、今度は、語彙集における形態のみに適用するように
限定される。この単一の合体されたＦＳＴは特に重要で
ある。というのは、ソース語彙を任意の数のルールトラ
ンスジューサと合成すると、言語の充分に形成されてい
る全てのワード形態を系統的な仕方で列挙する簡単なル
ックダウンアルゴリズムを形成できるからである。ルー
ルに基づく列挙は、テキストの集合体から導出したワー
ドリストよりも完全であり、語幹決定のような用途では
重要である。
が真の語幹であるかどうかに係わりなく又そうであった
としても、これら全てのストリングに文法の１組のルー
ルが適用される。これらルールは、特定の辞書もしくは
語彙集にリストされた項目のみに適用するように制約す
るのが望ましい。語彙集におけるワードのリストは、限
定状態マシンとして表すことができるので、この制約
は、ＦＳＴ合成演算子によって達成することができる。
語彙集の各ワードをそれ自身へとマップする同一トラン
スジューサが形成されるが、これは、例えば、ＦＳＭに
おける各遷移のラベルを、そのラベルの２つの場合を含
む対と置き換えることによって行うことができる。この
同一トランスジューサは、ルール及び不規則形態（図
６）を表すＦＳＴと合成される。これにより得たＦＳＴ
は、今度は、語彙集における形態のみに適用するように
限定される。この単一の合体されたＦＳＴは特に重要で
ある。というのは、ソース語彙を任意の数のルールトラ
ンスジューサと合成すると、言語の充分に形成されてい
る全てのワード形態を系統的な仕方で列挙する簡単なル
ックダウンアルゴリズムを形成できるからである。ルー
ルに基づく列挙は、テキストの集合体から導出したワー
ドリストよりも完全であり、語幹決定のような用途では
重要である。
【００４２】語彙を、交差によって結合したルールと合
成すべき場合には、本来の動作順序は、ルールの交差に
対してＦＳＴを形成し、そしてこれを語彙の同一トラン
スジューサと合成することである。このやり方が図９に
示されており、第１組のルールトランスジューサｆｓｔ
1 ．．．ｆｓｔn ６１、６２、６３が記号＆で示された
ように交差することが示されている。実際に、この交差
を行うには、強力なワークステーションにおいても多大
な時間を要し、それにより得られたトランスジューサは
かなり大きなものになることが分かった。多くの場合
に、この計算を行って完了させることはできない。とい
うのは、時間又はメモリに制約があるからである。しか
しながら、これを構成して（６４）語彙集６５と合成し
た（円記号で示す）ときには、最終的な結果６６は、そ
のサイズがかなり扱い易いものとなることも分かった。
これは、ＦＳＴを語彙のワードの特定リストのみに適用
するときには交差における多くの状態及び遷移が決して
進められず、合成手順において除去されるからである。
成すべき場合には、本来の動作順序は、ルールの交差に
対してＦＳＴを形成し、そしてこれを語彙の同一トラン
スジューサと合成することである。このやり方が図９に
示されており、第１組のルールトランスジューサｆｓｔ
1 ．．．ｆｓｔn ６１、６２、６３が記号＆で示された
ように交差することが示されている。実際に、この交差
を行うには、強力なワークステーションにおいても多大
な時間を要し、それにより得られたトランスジューサは
かなり大きなものになることが分かった。多くの場合
に、この計算を行って完了させることはできない。とい
うのは、時間又はメモリに制約があるからである。しか
しながら、これを構成して（６４）語彙集６５と合成し
た（円記号で示す）ときには、最終的な結果６６は、そ
のサイズがかなり扱い易いものとなることも分かった。
これは、ＦＳＴを語彙のワードの特定リストのみに適用
するときには交差における多くの状態及び遷移が決して
進められず、合成手順において除去されるからである。
【００４３】従って、語彙とルールの交差との合成とし
て作用するＦＳＴを形成するための本発明の好ましい方
法が図１０に示されている。この方法は、扱い難い大き
な中間構造体６４の計算を回避する一方、取り扱い易い
サイズの最終結果を生じるようにする。この例では、ル
ールトランスジューサ６１．．．６３の組が交差される
と同時に語彙形態６５と合成されて、所望の語彙トラン
スジューサ７０が形成される。この同時の交差及び合成
は、図９に６４で示した大きな中間結果を回避する。こ
れにより得られる語彙トランスジューサ７０は、所望の
合体したＦＳＴ７０であり、語彙をルールトランスジュ
ーサの交差と合成することにより論理的に定められたマ
ップである。
て作用するＦＳＴを形成するための本発明の好ましい方
法が図１０に示されている。この方法は、扱い難い大き
な中間構造体６４の計算を回避する一方、取り扱い易い
サイズの最終結果を生じるようにする。この例では、ル
ールトランスジューサ６１．．．６３の組が交差される
と同時に語彙形態６５と合成されて、所望の語彙トラン
スジューサ７０が形成される。この同時の交差及び合成
は、図９に６４で示した大きな中間結果を回避する。こ
れにより得られる語彙トランスジューサ７０は、所望の
合体したＦＳＴ７０であり、語彙をルールトランスジュ
ーサの交差と合成することにより論理的に定められたマ
ップである。
【００４４】本発明は、語幹決定を用いて情報を検索す
る新規な技術に関するものであることを理解されたい。
これはＦＳＴの使用に基づいている。必要な記憶量を減
少すると共に速度を高めるためにコンパクトなＦＳＴが
所望される。効率的なことから上記したようにあるコン
パクト化技術が好ましい−−そして本発明の重要な利点
はこのような好ましいコンパクト化構成を本発明の実施
に使用できることである−−が、本発明はこのような好
ましいコンパクト化構成の使用に限定されるものではな
く、本発明の原理から逸脱せずに実質上全てのコンパク
ト構成を組み込むことができる。
る新規な技術に関するものであることを理解されたい。
これはＦＳＴの使用に基づいている。必要な記憶量を減
少すると共に速度を高めるためにコンパクトなＦＳＴが
所望される。効率的なことから上記したようにあるコン
パクト化技術が好ましい−−そして本発明の重要な利点
はこのような好ましいコンパクト化構成を本発明の実施
に使用できることである−−が、本発明はこのような好
ましいコンパクト化構成の使用に限定されるものではな
く、本発明の原理から逸脱せずに実質上全てのコンパク
ト構成を組み込むことができる。
【００４５】図１１ないし１５から明らかなように、本
発明の情報検索における重要な利点は、公知の語幹決定
機構が典型的に表面形態から語幹への一方向にしか動作
しなかったのに対して、形成された単一の合体したＦＳ
Ｔ８０が両方向に動作できることである。これは、本発
明の融通性及び既存のデータベースへの利用性を著しく
高める。典型的な既存のデータベースは、ワードに対す
る文書の位置を指示する値のワードインデックスを有す
るものが多く、語幹インデックスを有するものではな
い。本発明は、次の２つの方法の１つで容易に追加する
ことができる。即ち、（１）合体したＦＳＴを使用し
て、ワードインデックスの語幹を予め決定しそしてその
ワードインデックスからの対応する値にリンクされた語
幹のみの新たなインデックスを形成する。図１１は、表
面形態の質問ワードが入力されたときに（８１）、ルッ
クアップアルゴリズムを適用して（８２）、質問ワード
からその語幹を形成することを示している。次いで、そ
の質問語幹にとの一致に対して新たな語幹インデックス
を走査することができる（８３）。この一致がユーザへ
出力される（８８）。（２）図１２に示すように、ルッ
クアップアルゴリズムを適用することにより入力ワード
の語幹を予め決定し（８２ｂ）、次いで、ＦＳＴを使用
する（８６）が、このときはルックダウンアルゴリズム
を用いてその語幹の全ての変化を発生する。その後、各
変化との一致を探して元のワードインデックスを走査す
る（８３ｂ）。（３）この第２のやり方に代わるものが
図１３に示されている。この場合は、合体したＦＳＴを
その逆構成のものと合成することにより形成した単一の
ＦＳＴにおいてルックアップアルゴリズムを実行するこ
とにより全ての語幹変化が形成される（８２ｃ）。この
別のやり方は、図１２の方法よりも高速であるが、ある
場合には、合成されるトランスジューサが実施するには
大きくなり過ぎることがある。いずれの場合にも、語幹
及びその変化を対称的に取り扱うＦＳＴの能力により、
関連ワードを含む文書の識別に著しい改善結果が得られ
る。従って、既存のデータベースは、それらのサーチ機
能を向上するのに特殊な処理を必要としない。更に別の
特別な利点として、ＦＳＴは優れた語幹決定機能を果た
し、形成される各語幹が完全な英語のワードであるよう
保証することができる。
発明の情報検索における重要な利点は、公知の語幹決定
機構が典型的に表面形態から語幹への一方向にしか動作
しなかったのに対して、形成された単一の合体したＦＳ
Ｔ８０が両方向に動作できることである。これは、本発
明の融通性及び既存のデータベースへの利用性を著しく
高める。典型的な既存のデータベースは、ワードに対す
る文書の位置を指示する値のワードインデックスを有す
るものが多く、語幹インデックスを有するものではな
い。本発明は、次の２つの方法の１つで容易に追加する
ことができる。即ち、（１）合体したＦＳＴを使用し
て、ワードインデックスの語幹を予め決定しそしてその
ワードインデックスからの対応する値にリンクされた語
幹のみの新たなインデックスを形成する。図１１は、表
面形態の質問ワードが入力されたときに（８１）、ルッ
クアップアルゴリズムを適用して（８２）、質問ワード
からその語幹を形成することを示している。次いで、そ
の質問語幹にとの一致に対して新たな語幹インデックス
を走査することができる（８３）。この一致がユーザへ
出力される（８８）。（２）図１２に示すように、ルッ
クアップアルゴリズムを適用することにより入力ワード
の語幹を予め決定し（８２ｂ）、次いで、ＦＳＴを使用
する（８６）が、このときはルックダウンアルゴリズム
を用いてその語幹の全ての変化を発生する。その後、各
変化との一致を探して元のワードインデックスを走査す
る（８３ｂ）。（３）この第２のやり方に代わるものが
図１３に示されている。この場合は、合体したＦＳＴを
その逆構成のものと合成することにより形成した単一の
ＦＳＴにおいてルックアップアルゴリズムを実行するこ
とにより全ての語幹変化が形成される（８２ｃ）。この
別のやり方は、図１２の方法よりも高速であるが、ある
場合には、合成されるトランスジューサが実施するには
大きくなり過ぎることがある。いずれの場合にも、語幹
及びその変化を対称的に取り扱うＦＳＴの能力により、
関連ワードを含む文書の識別に著しい改善結果が得られ
る。従って、既存のデータベースは、それらのサーチ機
能を向上するのに特殊な処理を必要としない。更に別の
特別な利点として、ＦＳＴは優れた語幹決定機能を果た
し、形成される各語幹が完全な英語のワードであるよう
保証することができる。
【００４６】図１１、１２及び１３に示された手順は、
ワードインデックスが存在しない文書データベースにも
適用できる。この状態においては、８３ｂ及び８３ｃで
走査されるデータベースは、データベース内の文書の全
テキストである。従って、質問ワードは１組の全ての変
化にまで拡張され、これらはデータベース内の全てのワ
ードと分離的に比較され、一致が決定される。図１１の
手順の変形態様を実施することもできる。即ち、質問ワ
ードに対する語幹がいったん計算され、そしてこれが文
書データベース内の各ワードの語幹（ルックアップアル
ゴリズムを用いて計算された）と比較される。これが図
１４に示されている。図１５は、トランスジューサを先
ず文書テキストのデータベースに適用して語幹インデッ
クスを構成し、次いで、その入力を特定の質問ワードの
語幹に対して一致させるやり方を示している。同様のブ
ロックは同じ参照番号で示してある。
ワードインデックスが存在しない文書データベースにも
適用できる。この状態においては、８３ｂ及び８３ｃで
走査されるデータベースは、データベース内の文書の全
テキストである。従って、質問ワードは１組の全ての変
化にまで拡張され、これらはデータベース内の全てのワ
ードと分離的に比較され、一致が決定される。図１１の
手順の変形態様を実施することもできる。即ち、質問ワ
ードに対する語幹がいったん計算され、そしてこれが文
書データベース内の各ワードの語幹（ルックアップアル
ゴリズムを用いて計算された）と比較される。これが図
１４に示されている。図１５は、トランスジューサを先
ず文書テキストのデータベースに適用して語幹インデッ
クスを構成し、次いで、その入力を特定の質問ワードの
語幹に対して一致させるやり方を示している。同様のブ
ロックは同じ参照番号で示してある。
【００４７】語幹決定手段として働くＦＳＴが、資格を
与える多数の語幹を発生できるような例がある。例え
ば、表面形態が「DOES」の場合には、語幹は「DO」とな
り（ここでは「DOES」は動詞として扱われる）、或いは
語幹は「DOE 」となる（ここでは「DOES」は複数の「de
er」として扱われる）。この状態を解決するのに種々の
ルールを適用することができる。１つの簡単な解決策は
両方の語幹を形成し、その各々をそれがあたかも唯一の
語幹であるかのように処理することであるが、最悪の場
合、識別される文書の数を増加させる。ここで従うこと
のできる１つのルールは、常に最も短い語幹を選択する
ことである。上記例の場合では、「DO」を選択するが、
これはその感染的形態の中に「DOE 」及び「DOES」を含
む。しかしながら、トランスジューサが形態学的分析器
として動作して、接辞及びスピーチ部分タグと語幹を発
生するように構成される場合には、スピーチ部分のあい
まいさを解消するための多数の公知技術の１つを使用し
て、特定の文章構成内で適当な語幹を選択することがで
きる。
与える多数の語幹を発生できるような例がある。例え
ば、表面形態が「DOES」の場合には、語幹は「DO」とな
り（ここでは「DOES」は動詞として扱われる）、或いは
語幹は「DOE 」となる（ここでは「DOES」は複数の「de
er」として扱われる）。この状態を解決するのに種々の
ルールを適用することができる。１つの簡単な解決策は
両方の語幹を形成し、その各々をそれがあたかも唯一の
語幹であるかのように処理することであるが、最悪の場
合、識別される文書の数を増加させる。ここで従うこと
のできる１つのルールは、常に最も短い語幹を選択する
ことである。上記例の場合では、「DO」を選択するが、
これはその感染的形態の中に「DOE 」及び「DOES」を含
む。しかしながら、トランスジューサが形態学的分析器
として動作して、接辞及びスピーチ部分タグと語幹を発
生するように構成される場合には、スピーチ部分のあい
まいさを解消するための多数の公知技術の１つを使用し
て、特定の文章構成内で適当な語幹を選択することがで
きる。
【００４８】本発明のＦＳＴは、図１のシステムを動作
することにより使用される。その実行中に、ＦＳＴは、
前記のように語幹決定又は発生のために処理され即ち進
められる。
することにより使用される。その実行中に、ＦＳＴは、
前記のように語幹決定又は発生のために処理され即ち進
められる。
【００４９】テキストインデックス及び検索に関する本
発明のトランスジューサ技術の更に別の利点は、次の通
りである。インデックスされるべき文書のテキストにお
けるワードは、種々の感染的形態で現れるのみならず、
種々の句読点文章、スペースやカンマやピリオド等に隣
接する大文字及び小文字、又は他のワードのアルファベ
ット文字にすぐ隣接したドイツ語やフィンランド語のよ
うな複合言語の形態でも現れる。インデックスされるべ
き個々のワードを作り上げている文字のまわりに特殊な
マーカを挿入し、全て小文字に変換し、そして他の全て
の余分な句読点マークを削除するだけでテキストを正規
化する限定状態トランスジューサを構成することができ
る。この正規化トランスジューサを語幹決定トランスジ
ューサと合成することにより、テキストの句読点付き文
字の流れをそれに対応する一連の語幹にマップするよう
な単一トランスジューサが形成される。
発明のトランスジューサ技術の更に別の利点は、次の通
りである。インデックスされるべき文書のテキストにお
けるワードは、種々の感染的形態で現れるのみならず、
種々の句読点文章、スペースやカンマやピリオド等に隣
接する大文字及び小文字、又は他のワードのアルファベ
ット文字にすぐ隣接したドイツ語やフィンランド語のよ
うな複合言語の形態でも現れる。インデックスされるべ
き個々のワードを作り上げている文字のまわりに特殊な
マーカを挿入し、全て小文字に変換し、そして他の全て
の余分な句読点マークを削除するだけでテキストを正規
化する限定状態トランスジューサを構成することができ
る。この正規化トランスジューサを語幹決定トランスジ
ューサと合成することにより、テキストの句読点付き文
字の流れをそれに対応する一連の語幹にマップするよう
な単一トランスジューサが形成される。
【００５０】図１７は、正規化ＦＳＴ９０を図１０の語
幹決定ＦＳＴ７０といかに合成する（９４）かについて
の本発明の更に別の特徴を示している。それにより、新
たな合体されたＦＳＴ９５が形成される。この新たな合
体されたＦＳＴ９５では、文書のテキストを表す文字の
流れを入力すると、１ステップ動作で対応する一連の語
幹へのマッピングが生じる（９７）。
幹決定ＦＳＴ７０といかに合成する（９４）かについて
の本発明の更に別の特徴を示している。それにより、新
たな合体されたＦＳＴ９５が形成される。この新たな合
体されたＦＳＴ９５では、文書のテキストを表す文字の
流れを入力すると、１ステップ動作で対応する一連の語
幹へのマッピングが生じる（９７）。
【００５１】好ましい実施例について本発明を詳細に説
明したが、本発明の精神から逸脱せずに種々の変更や修
正が当業者に明らかであろう。従って、本発明は、上記
した構造の細部に限定されるものではなく、特許請求の
範囲のみによって規定されるものとする。
明したが、本発明の精神から逸脱せずに種々の変更や修
正が当業者に明らかであろう。従って、本発明は、上記
した構造の細部に限定されるものではなく、特許請求の
範囲のみによって規定されるものとする。
【図１】本発明によるシステムの１つの形態を示すブロ
ック図である。
ック図である。
【図２】語幹とその変形との間のＦＳＴマッピングを示
す例である。
す例である。
【図３】言語を表す語彙集の例である。
【図４】言語を表す語彙集の例である。
【図５】言語を表す語彙集の例である。
【図６】言語を表す語彙集の例である。
【図７】ＦＳＴを合成して合体したＦＳＴを形成すると
ころを示す図である。
ころを示す図である。
【図８】２レベルルールＦＳＴを示す図である。
【図９】本発明による合体したＦＳＴの構成を示す図で
ある。
ある。
【図１０】本発明による合体したＦＳＴの構成を示す図
である。
である。
【図１１】本発明のシステムを動作するモードを示すア
ルゴリズムの図である。
ルゴリズムの図である。
【図１２】本発明のシステムを動作するモードを示すア
ルゴリズムの図である。
ルゴリズムの図である。
【図１３】本発明のシステムを動作するモードを示すア
ルゴリズムの図である。
ルゴリズムの図である。
【図１４】本発明のシステムを動作するモードを示すア
ルゴリズムの図である。
ルゴリズムの図である。
【図１５】本発明のシステムを動作するモードを示すア
ルゴリズムの図である。
ルゴリズムの図である。
【図１６】本発明により正規化ＦＳＴ及び合体したＦＳ
Ｔを用いて文字の流れを処理するところを示した図であ
る。
Ｔを用いて文字の流れを処理するところを示した図であ
る。
【図１７】本発明により正規化ＦＳＴ及び合体したＦＳ
Ｔを用いて文字の流れを処理するところを示した図であ
る。
Ｔを用いて文字の流れを処理するところを示した図であ
る。
【図１８】ＦＳＴをＦＳＭにいかに変換するかを示す図
である。
である。
【図１９】ワードと、その語幹、スピーチ部分及び形態
学的接辞タグとの間の簡単なＦＳＴマッピングを示す図
である。
学的接辞タグとの間の簡単なＦＳＴマッピングを示す図
である。
【図２０】文字ベースのＦＳＴがストリングベースのＦ
ＳＴより多くの初期サブストリング遷移をいかに分担で
きるかを示す図で、本発明の場合を示す図である。
ＳＴより多くの初期サブストリング遷移をいかに分担で
きるかを示す図で、本発明の場合を示す図である。
【図２１】文字ベースのＦＳＴがストリングベースのＦ
ＳＴより多くの初期サブストリング遷移をいかに分担で
きるかを示す図で、公知技術の場合を示す図である。
ＳＴより多くの初期サブストリング遷移をいかに分担で
きるかを示す図で、公知技術の場合を示す図である。
１０、１１、１２、１３ ＦＳＴ １５ 合体したＦＳＴ ３０ マシン ３１ メモリ ３２ ＣＰＵ ３６ モニタ
───────────────────────────────────────────────────── フロントページの続き (72)発明者 ペル クリスチャン ジー ハルヴォルセ ン アメリカ合衆国 カリフォルニア州 94022 ロス アルトス キャリーエイジ コート 11 (72)発明者 ロナルド エム カプラン アメリカ合衆国 カリフォルニア州 94306 パロ アルト オーム ストリー ト 5015 (72)発明者 ローリー カーテュネン アメリカ合衆国 カリフォルニア州 94062 レッドウッド シティー ジェフ ァーソン アベニュー 3950 (72)発明者 マーティン ケイ アメリカ合衆国 カリフォルニア州 94025 メンロ パーク ペニンシュラ ウェイ 935 (72)発明者 ジャン オー ペダーセン アメリカ合衆国 カリフォルニア州 94303 パロ アルト ビビッツ ドライ ヴ 3913
Claims (31)
- 【請求項１】 コンピュータ化した情報検索又はテキス
トインデックス装置において、 （ａ）データベースを具備し、このデータベースは語幹
の変化関係を表すデータ構造体を備え、このデータ構造
体は、複数の分岐路に沿って上部及び下部ストリングの
順序付けされた対の組をエンコードするための限定状態
トランスジューサ（ＦＳＴ）を備えており、各対の上部
ストリングはワードの語幹でありそして各対の下部スト
リングはワードの変化であり、これにより、１つの対の
上部ストリングを経てＦＳＴの分岐路を進むと、その対
の下部ストリングを検索することができ、或いは１つの
対の下部ストリングを経てＦＳＴの分岐路を進むと、そ
の対の上部ストリングを検索することができ、そして （ｂ）上記データベースに接続され、語幹又はその変化
を組み込んだワードを入力するユーザの質問に応答し
て、その質問ワードに一致する下部ストリングを有する
ＦＳＴ分岐路を経て完全な経路をサーチするようにデー
タ構造体のＦＳＴを進ませるための処理手段を更に具備
し、該処理手段は、分岐路を通る完全な経路を見つける
のに応答して、その分枝路により表された上部ストリン
グの語幹であって上記質問ワード又はそれを含む文書の
識別に対応する上部ストリングの語幹を出力するか、或
いは上記分岐路により表された別のワード変化であって
上記質問ワード又はこれを含む文書の識別と同じ語幹を
有する別のワード変化を出力するための手段を更に備え
たことを特徴とする装置。 - 【請求項２】 見つかった分岐路を通して、上記語幹が
ワード変化の別の語幹を識別し始めるところまで後方に
追跡する手段と、この同じ別の語幹を有するＦＳＴの第
２の分岐路を通る完全な経路をサーチするようにデータ
構造体のＦＳＴを進ませそしてこの第２の分岐路によっ
て表されたワード変化を出力するための手段とを更に備
えた請求項１に記載の装置。 - 【請求項３】 上記ＦＳＴは語幹／変化の対のみの分岐
路を備えている請求項１に記載の装置。 - 【請求項４】 上記ＦＳＴは言語学ルールによって表す
ことのできる系統的な感染的及び派生的なワード代替え
物を組み込んでおり、そして上記ＦＳＴは上記言語学ル
ールのコンパイルしたバージョンを組み込んでいる請求
項１に記載の装置。 - 【請求項５】 上記ＦＳＴは、不規則なワード対の限定
リストから導出した第１のトランスジューサと、規則的
な言語学ルール及び語幹から導出した第２トランスジュ
ーサとを、上記第１トランスジューサのドメインの補数
に対して同一トランスジューサを計算し、この同一トラ
ンスジューサを上記第２トランスジューサと予め合成
し、そしてその結果を第１トランスジューサと結合させ
ることにより合体したものを備えている請求項１に記載
の装置。 - 【請求項６】 メモリ手段を更に備え、上記データベー
スはこのメモリ手段に記憶される請求項１に記載の装
置。 - 【請求項７】 情報検索又はテキストインデックスのた
めのコンピュータに使用するデータベースを形成する方
法において、 （ａ）不規則なワード語幹と変化の対の第１リストを構
成する形態的語彙集を形成し、 （ｂ）上記語幹の規則的なワード変化を形成するように
ワード語幹に接辞を追加するのを制御するための言語ル
ールの第２リストを形成し、 （ｃ）上記形態的語彙集の第１リストから導出した第１
ＦＳＴを形成し、 （ｄ）上記言語学ルールの第２リストから導出した第２
ＦＳＴを形成し、 （ｅ）上記第１及び第２ＦＳＴの各々は、単一の開始状
態から一連の中間状態を通る遷移を経て異なる終了状態
へ至る複数のＦＳＴ経路を画成する複数の分岐路を備
え、各分岐路は、ワード語幹を構成する上部ストリング
の１文字又はゼロ記号と、上記ワード語幹のワード変化
を構成する下部ストリングの１文字又はゼロ記号とで成
る順序付けされた対からの完全な経路を形成し、 （ｆ）合成及び交差アルゴリズムを用いて上記第１及び
第２ＦＳＴをコンパイルしてこれらＦＳＴを結合し、 （ｇ）このコンパイルした第１及び第２のＦＳＴを合体
して単一ＦＳＴを形成し、この単一ＦＳＴは、ワードが
形態的語彙集における不規則ワードであって第１ＦＳＴ
の内容によって拒絶される場合を除いて上記段階（ｂ）
の言語学ルールに従うワードの語幹をその語幹の変化に
マップするものであり、そして （ｈ）上記段階（ｇ）で形成された単一ＦＳＴを所望の
データベースの一部として記憶する、 という段階を備えたことを特徴とする方法。 - 【請求項８】 コンピュータ化した情報検索又はテキス
トインデックス装置に使用されるものであって、 メモリ手段を具備し、 上記メモリ手段に記憶されるデータベースを具備し、こ
のデータベースは語幹とその変化の関係を表すためのデ
ータ構造体を備え、このデータ構造体は単一の結合され
た限定状態トランスジューサ（ＦＳＴ）を備えており、 上記ＦＳＴは、開始状態から一連の中間状態を通る遷移
を経て異なる終了状態へ至る複数のＦＳＴ経路を画成す
る複数の分岐路を備え、各分岐路は、ストリングを表す
上記開始状態から終了状態までの完全な経路を形成し、
上記遷移の各々は、ワード語幹を構成する上部ストリン
グの１文字又はゼロ記号と、上記ワード語幹のワード変
化を構成する下部ストリングの１文字又はゼロ記号とで
成る順序付けされた対を表し、 上記単一のＦＳＴは、形態的語彙集を形成する不規則な
ワード語幹と変化の対の第１リストから導出された第１
ＦＳＴと、上記語幹の規則的なワード変化を形成するよ
うにワード語幹に接辞を追加するのを制御するための言
語学ルールの第２リストから導出した第２ＦＳＴとを合
体したものを備えており、 上記単一ＦＳＴは、ワードが形態的語彙集における不規
則ワードであってこれによって拒絶される場合を除いて
上記言語学ルールに従うワードの語幹をその語幹の変化
にマップするものであり、 これにより、１つの対の上部ストリングを経てＦＳＴの
分岐路を進むと、その対の下部ストリングを検索するこ
とができ、或いは１つの対の下部ストリングを経てＦＳ
Ｔの分岐路を進むと、その対の上部ストリングを検索す
ることができることを特徴とする装置。 - 【請求項９】 上記単一ＦＳＴは、ＦＳＴを結合するた
めの合成及び交差アルゴリズムを用いてコンパイルする
ことによって形成されたものである請求項８に記載の装
置。 - 【請求項１０】 上記の合体は、上記第１ＦＳＴのドメ
インの補数に対して同一トランスジューサを計算し、こ
の同一トランスジューサを上記第２ＦＳＴと予め合成
し、そしてその結果を第１ＦＳＴと結合させることによ
り行われる請求項８に記載の装置。 - 【請求項１１】 言語の表面形態を語彙形態にマップす
るＦＳＴであって、上記言語の文書からテキストをイン
デックスしそして検索するのに使用するためのＦＳＴを
形成する方法において、 （ａ）上記言語の１つ以上のルールを定める第１ＦＳＴ
を構成し、 （ｂ）上記言語の１つ以上の別のルールを定める第２Ｆ
ＳＴを構成し、 （ｃ）不規則な言語ワードをそれらの語幹にマップする
か又は上記言語の１つ以上の更に別のルールを定める第
３ＦＳＴを構成し、 （ｄ）上記第３ＦＳＴと、上記第１及び第２ＦＳＴの交
差との合成を同時に計算して、上記第１、第２及び第３
ＦＳＴを合体する新たな単一の第４ＦＳＴを形成する、 という段階を備えたことを特徴とする方法。 - 【請求項１２】 上記段階（ｄ）は、１段階の操作とし
て行われる請求項１１に記載の方法。 - 【請求項１３】 第１ＦＳＴと、第２及び第３ＦＳＴの
交差とを同時に合成することにより形成した合体したＦ
ＳＴ。 - 【請求項１４】 第１ＦＳＴのドメインの補数に対する
同一トランスジューサを計算し、第２ＦＳＴと予め合成
し、そしてその結果を第１ＦＳＴと結合することにより
形成した合体したＦＳＴ。 - 【請求項１５】 上記第１ＦＳＴは、言語の不規則な語
幹とその変形のと対の限定リストから導出したトランス
ジューサであり、そして上記第２ＦＳＴは、上記言語を
定める通常のルールから導出したトランスジューサであ
り、この通常のルールの１つは、上記言語の不規則な語
幹とその変形との対の１つに適用される請求項１４に記
載の合体したＦＳＴ。 - 【請求項１６】 言語のデータベースを使用し、その言
語のワードの表面形態をその語彙の語幹へとマップする
ＦＳＴの助けにより、そのデータベースに記憶された言
語のワードからワードのインデックス及び検索をするた
めの方法において、 （ａ）上記データベースにおける関連ワード又はこのよ
うなワードを含む文書の識別を要求する言語のワードを
含む質問を入力し、 （ｂ）ＦＳＴをアップ方向に動作して質問ワードの語幹
を得ると共に、データベースを走査して、一致する語幹
を有するワードを探索し、或いは （ｃ）ＦＳＴをアップ方向に動作して質問ワードの語彙
の語幹を得、ＦＳＴをその語彙の語幹でダウン方向に動
作してその語彙の語幹の全ての変化を発生し、そしてこ
れら変化の各々でデータベースを走査して一致をサーチ
する、 という段階を備えたことを特徴とする方法。 - 【請求項１７】 一致が見つかった場合に、その一致又
はその一致を含む文書の識別を出力する請求項１６に記
載の方法。 - 【請求項１８】 文字の流れの入力に応答して、余計な
句読点マークのない小文字の個々のワードより成る正規
化したテキストを出力するための手段を備えたことを特
徴とする限定状態トランスジューサ。 - 【請求項１９】 文字の流れの入力に応答してそれに対
応する一連の語幹を出力するための合体されたトランス
ジューサを形成するように語幹決定トランスジューサと
合成された請求項１８に記載の限定状態トランスジュー
サ。 - 【請求項２０】 文書のテキストを正規化する方法にお
いて、 （ａ）正規化ＦＳＴを構成し、そして （ｂ）上記段階（ａ）のＦＳＴに文書テキストから導出
した文字の流れを入力しするという段階を備えたことを
特徴とする方法。 - 【請求項２１】 （ｃ）上記段階（ａ）の正規化ＦＳＴ
を語幹決定ＦＳＴと合成して、合体したＦＳＴを形成
し、そして （ｄ）文字の流れを上記段階（ｃ）の合体したＦＳＴに
入力するという段階を備えた請求項２０に記載の方法。 - 【請求項２２】 コンピュータ化した言語処理装置にお
いて、 （ａ）データベースを具備し、このデータベースは、語
幹とその変化との関係と、スピーチの変化部分と接辞と
の関係とを表すためのデータ構造体を備え、このデータ
構造体は、複数の分岐路に沿って上部及び下部ラベルの
順序付けされた対とスピーチ部分又は接辞のタグ／ラベ
ルとの組をエンコードするための結合した限定状態トラ
ンスジューサ（ＦＳＴ）を備えており、各対の上部スト
リングはワードの語幹或いはスピーチの部分又は接辞タ
グの文字であり、各対の下部ストリングはワード変化又
はゼロの文字であり、これにより、上部対を経てＦＳＴ
の分岐路を進むと、その下部対を検索することができ、
或いは下部対を経てＦＳＴの分岐路を進むと、その上部
対を検索することができ、そして （ｂ）上記データベースに接続され、語幹又はその変化
を組み込んだワードを入力するユーザの質問に応答し
て、その質問ワードに一致する下部対を有するＦＳＴ分
岐路を経て完全な経路をサーチするようにデータ構造体
のＦＳＴを進ませるための処理手段を更に具備し、該処
理手段は、分岐路を通る完全な経路を見つけるのに応答
して、その分枝路により表された上部ストリングの語幹
又はスピーチ部分であって上記質問ワード又はそれを含
む文書の識別に対応するような上部ストリングの語幹ス
ピーチ部分を出力するか、或いは上記分岐路により表さ
れた別のワード変化であって上記質問ワード又はこれを
含む文書の識別と同じ語幹を有するような別のワード変
化を出力するための手段を更に備えたことを特徴とする
装置。 - 【請求項２３】 コンピュータ化した言語処理装置に使
用されるもので、 メモリ手段を具備し、 上記メモリ手段に記憶されるデータベースを具備し、こ
のデータベースは語幹とその変化との関係と、スピーチ
の変化部分と接辞との関係をタグとして表すためのデー
タ構造体を備え、このデータ構造体は単一の結合された
限定状態トランスジューサ（ＦＳＴ）を備えており、 上記ＦＳＴは、単一の開始状態から一連の中間状態を通
る遷移を経て異なる終了状態へ至る複数のＦＳＴ経路を
画成する複数の分岐路を備え、各分岐路は、ストリング
又はストリングとタグを表す上記開始状態から終了状態
までの完全な経路を形成し、上記遷移の各々は、ワード
語幹か或いはスピーチの部分又は接辞の関係を表すラベ
ルかを構成する上部ストリングの１文字又はゼロ記号
と、上記ワード語幹のワード変化を構成する下部ストリ
ングの１文字又はゼロ記号とで成る順序付けされた対を
表し、 上記単一のＦＳＴは、形態的語彙集を形成する不規則な
ワード語幹と変化との対の第１リストから導出された第
１ＦＳＴと、言語学ルールの第２リストから導出した第
２ＦＳＴとを合体したものを備えており、 これにより、１つの対の上部ストリングを経てＦＳＴの
分岐路を進むと、その対の下部ストリングを検索するこ
とができ、或いは１つの対の下部ストリングを経てＦＳ
Ｔの分岐路を進むと、その対の上部ストリング又はタグ
をもつ上部ストリングを検索することができることを特
徴とする装置。 - 【請求項２４】 上記単一のＦＳＴは、ＦＳＴを結合す
るように合成及び交差アルゴリズムを用いてコンパイル
することにより形成されたものである請求項２３に記載
の装置。 - 【請求項２５】 言語の表面形態を語彙形態にマップす
るＦＳＴであって、上記言語の文書からテキストをイン
デックスしそして検索するのに使用するか又は他の言語
処理用途に使用するためのＦＳＴを形成する方法におい
て、 （ａ）上記言語の１つ以上のルールを定める第１ＦＳＴ
を構成し、 （ｂ）上記言語の表面形態を、スピーチの部分又は接辞
タグを含む語彙の形態にマップする第２ＦＳＴを構成
し、そして （ｃ）上記第２ＦＳＴと上記第１ＦＳＴとの合成を計算
して、上記第１及び第２ＦＳＴを合体する新たな単一の
第３ＦＳＴを形成する、 という段階を備えたことを特徴とする方法。 - 【請求項２６】 請求項２５に記載の合体したＦＳＴ。
- 【請求項２７】 言語のデータベースを使用し、その言
語のワードの表面形態をその語彙の対応部分形態へとマ
ップするＦＳＴの助けにより、その言語の文書からワー
ドをインデックス及び検索するか又は他の言語処理に用
いる方法において、 （ａ）上記データベースにおける関連ワードか又はこの
ようなワードを含む文書か或いはスピーチの質問ワード
部分かの識別を要求する言語のワードを含む質問を入力
し、 （ｂ）ＦＳＴをアップ方向に動作して質問ワードの語幹
を得ると共に、データベースを走査して、一致する語幹
を探索し、或いは （ｃ）ＦＳＴをアップ方向に動作して質問ワードの語彙
の対応部分を得、この語彙の対応部分でＦＳＴをダウン
方向に動作してその語彙の対応部分の全ての変化を生じ
させ、そしてこれら変化の各々でデータベースを走査し
て一致をサーチし、或いは （ｄ）ＦＳＴをアップ方向に動作して質問ワードのスピ
ーチ部分を得る、 という段階を備えたことを特徴とする方法。 - 【請求項２８】 一致が見つかった場合に、その一致又
はこれを含む文書の識別を出力する請求項２７に記載の
方法。 - 【請求項２９】 上記ＦＳＴは圧縮される請求項１に記
載の装置。 - 【請求項３０】 上記データ構造体は、圧縮されたＦＳ
Ｔである請求項８に記載の装置。 - 【請求項３１】 コンピュータ化した言語処理装置にお
いて、 （ａ）データベースを具備し、このデータベースは、語
幹とその変化との関係と、スピーチの変化部分と接辞と
の関係とを表すためのデータ構造体を備え、このデータ
構造体は、限定状態トランスジューサ（ＦＳＴ）から変
換した結合限定状態マシン（ＦＳＭ）を備え、上記ＦＳ
Ｔの各々は、上部及び下部ラベルと、スピーチの部分又
は接辞タグラベルとの順序付けされた対の組を複数の分
岐路に沿ってエンコードするものであり、各対の上部ス
トリングは、ワードの語幹或いはスピーチ部分又は接辞
タグ又はゼロの文字であり、各対の下部ストリングは、
ワード変化又はゼロの文字であり、元の状態から行き先
状態への上記ＦＳＴ遷移の各々は、上記ＦＳＴにおい
て、上部ストリングのラベル又はタグ又はゼロを表すよ
うに表示されて新たな状態へと至る奇数番号の遷移と置
き換えられ、その後、下部ストリング文字又はゼロを表
すように表示されて上記新たな状態から上記行き先状態
へと至る偶数番号遷移と置き換えられ、これにより、奇
数番号の遷移を経てＦＳＴの分岐路を進むと、その下部
ストリングの文字を検索でき、又は偶数番号の遷移を経
てＦＳＴの分岐路を進むと、上部ストリングのラベル又
はタグを検索でき、そして （ｂ）上記データベースに接続され、語幹又はその変化
を組み込んだワードを入力するユーザの質問に応答し
て、その質問ワードに一致する下部文字を有するＦＳＴ
分岐路を経て完全な経路をサーチするようにデータ構造
体のＦＳＴを進ませるための処理手段を更に具備し、該
処理手段は、分岐路を通る完全な経路を見つけるのに応
答して、その分枝路により表された上部ストリングの語
幹又はスピーチ部分であって上記質問ワード又はそれを
含む文書の識別に対応するような上部ストリングの語幹
スピーチ部分を出力するか、或いは上記分岐路により表
された別のワード変化であって上記質問ワード又はこれ
を含む文書の識別と同じ語幹を有するような別のワード
変化を出力するための手段を更に備えたことを特徴とす
る装置。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US07/916,576 US5625554A (en) | 1992-07-20 | 1992-07-20 | Finite-state transduction of related word forms for text indexing and retrieval |
| US07/916576 | 1992-07-20 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0675992A true JPH0675992A (ja) | 1994-03-18 |
| JP3196868B2 JP3196868B2 (ja) | 2001-08-06 |
Family
ID=25437499
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP15980493A Expired - Fee Related JP3196868B2 (ja) | 1992-07-20 | 1993-06-30 | テキストをインデックス及び検索するための関連ワード形態の限定状態トランスジューサ |
Country Status (5)
| Country | Link |
|---|---|
| US (2) | US5625554A (ja) |
| EP (1) | EP0583083B1 (ja) |
| JP (1) | JP3196868B2 (ja) |
| DE (1) | DE69331209T2 (ja) |
| ES (1) | ES2168267T3 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0785047A (ja) * | 1993-08-02 | 1995-03-31 | Xerox Corp | コンパクトにエンコードされて記憶されたストリングの組を有する製品 |
Families Citing this family (212)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5680628A (en) * | 1995-07-19 | 1997-10-21 | Inso Corporation | Method and apparatus for automated search and retrieval process |
| US5794177A (en) * | 1995-07-19 | 1998-08-11 | Inso Corporation | Method and apparatus for morphological analysis and generation of natural language text |
| US5721939A (en) * | 1995-08-03 | 1998-02-24 | Xerox Corporation | Method and apparatus for tokenizing text |
| GB9524136D0 (en) | 1995-11-23 | 1996-01-24 | Xerox Corp | Indexing a database by finite-state transducer |
| US5828999A (en) * | 1996-05-06 | 1998-10-27 | Apple Computer, Inc. | Method and system for deriving a large-span semantic language model for large-vocabulary recognition systems |
| GB2314433A (en) * | 1996-06-22 | 1997-12-24 | Xerox Corp | Finding and modifying strings of a regular language in a text |
| US5778375A (en) * | 1996-06-27 | 1998-07-07 | Microsoft Corporation | Database normalizing system |
| US6498921B1 (en) * | 1999-09-01 | 2002-12-24 | Chi Fai Ho | Method and system to answer a natural-language question |
| US5836771A (en) * | 1996-12-02 | 1998-11-17 | Ho; Chi Fai | Learning method and system based on questioning |
| CA2226233C (en) * | 1997-01-21 | 2006-05-09 | At&T Corp. | Systems and methods for determinizing and minimizing a finite state transducer for speech recognition |
| US5924105A (en) * | 1997-01-27 | 1999-07-13 | Michigan State University | Method and product for determining salient features for use in information searching |
| GB9713019D0 (en) | 1997-06-20 | 1997-08-27 | Xerox Corp | Linguistic search system |
| US6032111A (en) * | 1997-06-23 | 2000-02-29 | At&T Corp. | Method and apparatus for compiling context-dependent rewrite rules and input strings |
| US6026398A (en) * | 1997-10-16 | 2000-02-15 | Imarket, Incorporated | System and methods for searching and matching databases |
| GB9727322D0 (en) | 1997-12-29 | 1998-02-25 | Xerox Corp | Multilingual information retrieval |
| US6424983B1 (en) * | 1998-05-26 | 2002-07-23 | Global Information Research And Technologies, Llc | Spelling and grammar checking system |
| US6584479B2 (en) * | 1998-06-17 | 2003-06-24 | Xerox Corporation | Overlay presentation of textual and graphical annotations |
| US6173441B1 (en) | 1998-10-16 | 2001-01-09 | Peter A. Klein | Method and system for compiling source code containing natural language instructions |
| US6304878B1 (en) | 1998-11-23 | 2001-10-16 | Microsoft Corporation | Method and system for improved enumeration of tries |
| US6298321B1 (en) * | 1998-11-23 | 2001-10-02 | Microsoft Corporation | Trie compression using substates and utilizing pointers to replace or merge identical, reordered states |
| US6466901B1 (en) * | 1998-11-30 | 2002-10-15 | Apple Computer, Inc. | Multi-language document search and retrieval system |
| US6308149B1 (en) * | 1998-12-16 | 2001-10-23 | Xerox Corporation | Grouping words with equivalent substrings by automatic clustering based on suffix relationships |
| US6430557B1 (en) | 1998-12-16 | 2002-08-06 | Xerox Corporation | Identifying a group of words using modified query words obtained from successive suffix relationships |
| US6434546B1 (en) * | 1998-12-22 | 2002-08-13 | Xerox Corporation | System and method for transferring attribute values between search queries in an information retrieval system |
| US6381598B1 (en) * | 1998-12-22 | 2002-04-30 | Xerox Corporation | System for providing cross-lingual information retrieval |
| KR100828884B1 (ko) * | 1999-03-05 | 2008-05-09 | 캐논 가부시끼가이샤 | 데이터베이스 주석 및 검색 |
| US6742164B1 (en) * | 1999-09-01 | 2004-05-25 | International Business Machines Corporation | Method, system, and program for generating a deterministic table to determine boundaries between characters |
| US6675169B1 (en) | 1999-09-07 | 2004-01-06 | Microsoft Corporation | Method and system for attaching information to words of a trie |
| CN1329861C (zh) * | 1999-10-28 | 2007-08-01 | 佳能株式会社 | 模式匹配方法和装置 |
| US7310600B1 (en) | 1999-10-28 | 2007-12-18 | Canon Kabushiki Kaisha | Language recognition using a similarity measure |
| US6882970B1 (en) | 1999-10-28 | 2005-04-19 | Canon Kabushiki Kaisha | Language recognition using sequence frequency |
| US8645137B2 (en) | 2000-03-16 | 2014-02-04 | Apple Inc. | Fast, language-independent method for user authentication by voice |
| US6859800B1 (en) | 2000-04-26 | 2005-02-22 | Global Information Research And Technologies Llc | System for fulfilling an information need |
| US7120627B1 (en) * | 2000-04-26 | 2006-10-10 | Global Information Research And Technologies, Llc | Method for detecting and fulfilling an information need corresponding to simple queries |
| US20020123994A1 (en) * | 2000-04-26 | 2002-09-05 | Yves Schabes | System for fulfilling an information need using extended matching techniques |
| WO2001084376A2 (en) * | 2000-04-28 | 2001-11-08 | Global Information Research And Technologies Llc | System for answering natural language questions |
| US6704728B1 (en) | 2000-05-02 | 2004-03-09 | Iphase.Com, Inc. | Accessing information from a collection of data |
| US8478732B1 (en) | 2000-05-02 | 2013-07-02 | International Business Machines Corporation | Database aliasing in information access system |
| US6711561B1 (en) | 2000-05-02 | 2004-03-23 | Iphrase.Com, Inc. | Prose feedback in information access system |
| GB0011798D0 (en) * | 2000-05-16 | 2000-07-05 | Canon Kk | Database annotation and retrieval |
| US7031908B1 (en) * | 2000-06-01 | 2006-04-18 | Microsoft Corporation | Creating a language model for a language processing system |
| US6408277B1 (en) | 2000-06-21 | 2002-06-18 | Banter Limited | System and method for automatic task prioritization |
| US8290768B1 (en) | 2000-06-21 | 2012-10-16 | International Business Machines Corporation | System and method for determining a set of attributes based on content of communications |
| GB0015233D0 (en) | 2000-06-21 | 2000-08-16 | Canon Kk | Indexing method and apparatus |
| US9699129B1 (en) | 2000-06-21 | 2017-07-04 | International Business Machines Corporation | System and method for increasing email productivity |
| US20020072933A1 (en) * | 2000-06-30 | 2002-06-13 | Vonk Glenn Philander | Health outcomes and disease management network and related method for providing improved patient care |
| US20020152202A1 (en) * | 2000-08-30 | 2002-10-17 | Perro David J. | Method and system for retrieving information using natural language queries |
| CA2423964A1 (en) * | 2000-09-29 | 2002-04-04 | Gavagai Technology Incorporated | A method and system for describing and identifying concepts in natural language text for information retrieval and processing |
| GB0023930D0 (en) | 2000-09-29 | 2000-11-15 | Canon Kk | Database annotation and retrieval |
| GB0027178D0 (en) | 2000-11-07 | 2000-12-27 | Canon Kk | Speech processing system |
| US7010476B2 (en) * | 2000-12-18 | 2006-03-07 | Xerox Corporation | Method and apparatus for constructing finite-state networks modeling non-concatenative processes |
| US7644057B2 (en) * | 2001-01-03 | 2010-01-05 | International Business Machines Corporation | System and method for electronic communication management |
| US6938046B2 (en) * | 2001-03-02 | 2005-08-30 | Dow Jones Reuters Business Interactive, Llp | Polyarchical data indexing and automatically generated hierarchical data indexing paths |
| US7251625B2 (en) * | 2001-10-02 | 2007-07-31 | Best Buy Enterprise Services, Inc. | Customer identification system and method |
| US6785643B2 (en) * | 2001-10-15 | 2004-08-31 | Motorola, Inc. | Chart parsing using compacted grammar representations |
| US7181386B2 (en) * | 2001-11-15 | 2007-02-20 | At&T Corp. | Systems and methods for generating weighted finite-state automata representing grammars |
| EP1331630A3 (en) * | 2002-01-07 | 2006-12-20 | AT&T Corp. | Systems and methods for generating weighted finite-state automata representing grammars |
| US7289948B1 (en) * | 2002-01-07 | 2007-10-30 | At&T Corp. | Systems and methods for regularly approximating context-free grammars through transformation |
| AU2003214975A1 (en) * | 2002-02-01 | 2003-09-02 | John Fairweather | System and method for navigating data |
| US7343372B2 (en) * | 2002-02-22 | 2008-03-11 | International Business Machines Corporation | Direct navigation for information retrieval |
| US7240004B1 (en) * | 2002-03-04 | 2007-07-03 | At&T Corp. | Systems and methods for determining the determinizability of finite-state automata and transducers |
| GB0228942D0 (en) * | 2002-12-12 | 2003-01-15 | Ibm | Linguistic dictionary and method for production thereof |
| US7552051B2 (en) * | 2002-12-13 | 2009-06-23 | Xerox Corporation | Method and apparatus for mapping multiword expressions to identifiers using finite-state networks |
| US20050187913A1 (en) * | 2003-05-06 | 2005-08-25 | Yoram Nelken | Web-based customer service interface |
| US8495002B2 (en) * | 2003-05-06 | 2013-07-23 | International Business Machines Corporation | Software tool for training and testing a knowledge base |
| JP3956368B2 (ja) * | 2003-10-16 | 2007-08-08 | インターナショナル・ビジネス・マシーンズ・コーポレーション | 形態素解析システム |
| US7617091B2 (en) * | 2003-11-14 | 2009-11-10 | Xerox Corporation | Method and apparatus for processing natural language using tape-intersection |
| US7194450B2 (en) * | 2003-12-19 | 2007-03-20 | Xerox Corporation | Systems and methods for indexing each level of the inner structure of a string over a language having a vocabulary and a grammar |
| US6915300B1 (en) * | 2003-12-19 | 2005-07-05 | Xerox Corporation | Method and system for searching indexed string containing a search string |
| EP1677208A1 (en) * | 2004-12-30 | 2006-07-05 | Sap Ag | Method and system for searching for data objects |
| US20060149767A1 (en) * | 2004-12-30 | 2006-07-06 | Uwe Kindsvogel | Searching for data objects |
| US20060195313A1 (en) * | 2005-02-25 | 2006-08-31 | Microsoft Corporation | Method and system for selecting and conjugating a verb |
| US7937396B1 (en) | 2005-03-23 | 2011-05-03 | Google Inc. | Methods and systems for identifying paraphrases from an index of information items and associated sentence fragments |
| US8677377B2 (en) | 2005-09-08 | 2014-03-18 | Apple Inc. | Method and apparatus for building an intelligent automated assistant |
| US7937265B1 (en) | 2005-09-27 | 2011-05-03 | Google Inc. | Paraphrase acquisition |
| US20080213047A1 (en) * | 2006-08-21 | 2008-09-04 | Bryant Corwin J | Systems and methods for liner tensioning in pipeline rehabilitation |
| US9318108B2 (en) | 2010-01-18 | 2016-04-19 | Apple Inc. | Intelligent automated assistant |
| US8798988B1 (en) * | 2006-10-24 | 2014-08-05 | Google Inc. | Identifying related terms in different languages |
| US8041730B1 (en) | 2006-10-24 | 2011-10-18 | Google Inc. | Using geographic data to identify correlated geographic synonyms |
| US7925498B1 (en) | 2006-12-29 | 2011-04-12 | Google Inc. | Identifying a synonym with N-gram agreement for a query phrase |
| US8661012B1 (en) | 2006-12-29 | 2014-02-25 | Google Inc. | Ensuring that a synonym for a query phrase does not drop information present in the query phrase |
| US7890521B1 (en) * | 2007-02-07 | 2011-02-15 | Google Inc. | Document-based synonym generation |
| US20080208566A1 (en) * | 2007-02-23 | 2008-08-28 | Microsoft Corporation | Automated word-form transformation and part of speech tag assignment |
| US8977255B2 (en) | 2007-04-03 | 2015-03-10 | Apple Inc. | Method and system for operating a multi-function portable electronic device using voice-activation |
| US8037086B1 (en) | 2007-07-10 | 2011-10-11 | Google Inc. | Identifying common co-occurring elements in lists |
| US8001136B1 (en) | 2007-07-10 | 2011-08-16 | Google Inc. | Longest-common-subsequence detection for common synonyms |
| CN101689190A (zh) * | 2007-07-10 | 2010-03-31 | 国际商业机器公司 | 用于智能文本注释的方法、系统和计算机程序 |
| US8122022B1 (en) | 2007-08-10 | 2012-02-21 | Google Inc. | Abbreviation detection for common synonym generation |
| US9330720B2 (en) | 2008-01-03 | 2016-05-03 | Apple Inc. | Methods and apparatus for altering audio output signals |
| US8521516B2 (en) * | 2008-03-26 | 2013-08-27 | Google Inc. | Linguistic key normalization |
| US8996376B2 (en) | 2008-04-05 | 2015-03-31 | Apple Inc. | Intelligent text-to-speech conversion |
| US10496753B2 (en) | 2010-01-18 | 2019-12-03 | Apple Inc. | Automatically adapting user interfaces for hands-free interaction |
| US9002899B2 (en) * | 2008-07-07 | 2015-04-07 | International Business Machines Corporation | Method of merging and incremental construction of minimal finite state machines |
| US20100030549A1 (en) | 2008-07-31 | 2010-02-04 | Lee Michael M | Mobile device having human language translation capability with positional feedback |
| US8326785B2 (en) * | 2008-09-30 | 2012-12-04 | Microsoft Corporation | Joint ranking model for multilingual web search |
| US9959870B2 (en) | 2008-12-11 | 2018-05-01 | Apple Inc. | Speech recognition involving a mobile device |
| US8224839B2 (en) * | 2009-04-07 | 2012-07-17 | Microsoft Corporation | Search query extension |
| US10241752B2 (en) | 2011-09-30 | 2019-03-26 | Apple Inc. | Interface for a virtual digital assistant |
| US10241644B2 (en) | 2011-06-03 | 2019-03-26 | Apple Inc. | Actionable reminder entries |
| US10706373B2 (en) | 2011-06-03 | 2020-07-07 | Apple Inc. | Performing actions associated with task items that represent tasks to perform |
| US9858925B2 (en) | 2009-06-05 | 2018-01-02 | Apple Inc. | Using context information to facilitate processing of commands in a virtual assistant |
| US9431006B2 (en) | 2009-07-02 | 2016-08-30 | Apple Inc. | Methods and apparatuses for automatic speech recognition |
| US9009163B2 (en) * | 2009-12-08 | 2015-04-14 | Intellectual Ventures Fund 83 Llc | Lazy evaluation of semantic indexing |
| US10276170B2 (en) | 2010-01-18 | 2019-04-30 | Apple Inc. | Intelligent automated assistant |
| US10705794B2 (en) | 2010-01-18 | 2020-07-07 | Apple Inc. | Automatically adapting user interfaces for hands-free interaction |
| US10553209B2 (en) | 2010-01-18 | 2020-02-04 | Apple Inc. | Systems and methods for hands-free notification summaries |
| US10679605B2 (en) | 2010-01-18 | 2020-06-09 | Apple Inc. | Hands-free list-reading by intelligent automated assistant |
| DE202011111062U1 (de) | 2010-01-25 | 2019-02-19 | Newvaluexchange Ltd. | Vorrichtung und System für eine Digitalkonversationsmanagementplattform |
| US20110184959A1 (en) * | 2010-01-25 | 2011-07-28 | Palo Alto Research Center Incorporated | Summarizing medical content with iterative simplification rules |
| EP2534585A4 (en) * | 2010-02-12 | 2018-01-24 | Google LLC | Compound splitting |
| US8682667B2 (en) | 2010-02-25 | 2014-03-25 | Apple Inc. | User profiling for selecting user specific voice input processing information |
| US8543374B2 (en) * | 2010-08-12 | 2013-09-24 | Xerox Corporation | Translation system combining hierarchical and phrase-based models |
| US8484010B2 (en) | 2010-11-17 | 2013-07-09 | Technology Innovations, Llc | Method for designing an aptamer |
| US8527518B2 (en) * | 2010-12-16 | 2013-09-03 | Sap Ag | Inverted indexes with multiple language support |
| US10762293B2 (en) | 2010-12-22 | 2020-09-01 | Apple Inc. | Using parts-of-speech tagging and named entity recognition for spelling correction |
| US9262612B2 (en) | 2011-03-21 | 2016-02-16 | Apple Inc. | Device access using voice authentication |
| US10057736B2 (en) | 2011-06-03 | 2018-08-21 | Apple Inc. | Active transport based notifications |
| US8994660B2 (en) | 2011-08-29 | 2015-03-31 | Apple Inc. | Text correction processing |
| US10134385B2 (en) | 2012-03-02 | 2018-11-20 | Apple Inc. | Systems and methods for name pronunciation |
| US9483461B2 (en) | 2012-03-06 | 2016-11-01 | Apple Inc. | Handling speech synthesis of content for multiple languages |
| US9201946B2 (en) | 2012-04-26 | 2015-12-01 | Quixey, Inc. | Application representation for application editions |
| US9280610B2 (en) | 2012-05-14 | 2016-03-08 | Apple Inc. | Crowd sourcing information to fulfill user requests |
| US9721563B2 (en) | 2012-06-08 | 2017-08-01 | Apple Inc. | Name recognition system |
| US9495129B2 (en) | 2012-06-29 | 2016-11-15 | Apple Inc. | Device, method, and user interface for voice-activated navigation and browsing of a document |
| US9576574B2 (en) | 2012-09-10 | 2017-02-21 | Apple Inc. | Context-sensitive handling of interruptions by intelligent digital assistant |
| US9547647B2 (en) | 2012-09-19 | 2017-01-17 | Apple Inc. | Voice-based media searching |
| US9594744B2 (en) * | 2012-11-28 | 2017-03-14 | Google Inc. | Speech transcription including written text |
| KR20250004158A (ko) | 2013-02-07 | 2025-01-07 | 애플 인크. | 디지털 어시스턴트를 위한 음성 트리거 |
| US9368114B2 (en) | 2013-03-14 | 2016-06-14 | Apple Inc. | Context-sensitive handling of interruptions |
| WO2014144579A1 (en) | 2013-03-15 | 2014-09-18 | Apple Inc. | System and method for updating an adaptive speech recognition model |
| US9922642B2 (en) | 2013-03-15 | 2018-03-20 | Apple Inc. | Training an at least partial voice command system |
| US20140337355A1 (en) * | 2013-05-13 | 2014-11-13 | Gnoetics, Inc. | Indexed Natural Language Processing |
| US9582608B2 (en) | 2013-06-07 | 2017-02-28 | Apple Inc. | Unified ranking with entropy-weighted information for phrase-based semantic auto-completion |
| WO2014197334A2 (en) | 2013-06-07 | 2014-12-11 | Apple Inc. | System and method for user-specified pronunciation of words for speech synthesis and recognition |
| WO2014197336A1 (en) | 2013-06-07 | 2014-12-11 | Apple Inc. | System and method for detecting errors in interactions with a voice-based digital assistant |
| WO2014197335A1 (en) | 2013-06-08 | 2014-12-11 | Apple Inc. | Interpreting and acting upon commands that involve sharing information with remote devices |
| HK1220268A1 (zh) | 2013-06-09 | 2017-04-28 | 苹果公司 | 用於實現跨數字助理的兩個或更多個實例的會話持續性的設備、方法、和圖形用戶界面 |
| US10176167B2 (en) | 2013-06-09 | 2019-01-08 | Apple Inc. | System and method for inferring user intent from speech inputs |
| JP2016521948A (ja) | 2013-06-13 | 2016-07-25 | アップル インコーポレイテッド | 音声コマンドによって開始される緊急電話のためのシステム及び方法 |
| US10791216B2 (en) | 2013-08-06 | 2020-09-29 | Apple Inc. | Auto-activating smart responses based on activities from remote devices |
| US9620105B2 (en) | 2014-05-15 | 2017-04-11 | Apple Inc. | Analyzing audio input for efficient speech and music recognition |
| US10592095B2 (en) | 2014-05-23 | 2020-03-17 | Apple Inc. | Instantaneous speaking of content on touch devices |
| US9502031B2 (en) | 2014-05-27 | 2016-11-22 | Apple Inc. | Method for supporting dynamic grammars in WFST-based ASR |
| US10289433B2 (en) | 2014-05-30 | 2019-05-14 | Apple Inc. | Domain specific language for encoding assistant dialog |
| US10170123B2 (en) | 2014-05-30 | 2019-01-01 | Apple Inc. | Intelligent assistant for home automation |
| US9715875B2 (en) | 2014-05-30 | 2017-07-25 | Apple Inc. | Reducing the need for manual start/end-pointing and trigger phrases |
| US10078631B2 (en) | 2014-05-30 | 2018-09-18 | Apple Inc. | Entropy-guided text prediction using combined word and character n-gram language models |
| US9734193B2 (en) | 2014-05-30 | 2017-08-15 | Apple Inc. | Determining domain salience ranking from ambiguous words in natural speech |
| US9842101B2 (en) | 2014-05-30 | 2017-12-12 | Apple Inc. | Predictive conversion of language input |
| US9966065B2 (en) | 2014-05-30 | 2018-05-08 | Apple Inc. | Multi-command single utterance input method |
| US9633004B2 (en) | 2014-05-30 | 2017-04-25 | Apple Inc. | Better resolution when referencing to concepts |
| US9430463B2 (en) | 2014-05-30 | 2016-08-30 | Apple Inc. | Exemplar-based natural language processing |
| US9760559B2 (en) | 2014-05-30 | 2017-09-12 | Apple Inc. | Predictive text input |
| US9785630B2 (en) | 2014-05-30 | 2017-10-10 | Apple Inc. | Text prediction using combined word N-gram and unigram language models |
| US10659851B2 (en) | 2014-06-30 | 2020-05-19 | Apple Inc. | Real-time digital assistant knowledge updates |
| US9338493B2 (en) | 2014-06-30 | 2016-05-10 | Apple Inc. | Intelligent automated assistant for TV user interactions |
| US10446141B2 (en) | 2014-08-28 | 2019-10-15 | Apple Inc. | Automatic speech recognition based on user feedback |
| US9818400B2 (en) | 2014-09-11 | 2017-11-14 | Apple Inc. | Method and apparatus for discovering trending terms in speech requests |
| US10789041B2 (en) | 2014-09-12 | 2020-09-29 | Apple Inc. | Dynamic thresholds for always listening speech trigger |
| US10074360B2 (en) | 2014-09-30 | 2018-09-11 | Apple Inc. | Providing an indication of the suitability of speech recognition |
| US9886432B2 (en) | 2014-09-30 | 2018-02-06 | Apple Inc. | Parsimonious handling of word inflection via categorical stem + suffix N-gram language models |
| US10127911B2 (en) | 2014-09-30 | 2018-11-13 | Apple Inc. | Speaker identification and unsupervised speaker adaptation techniques |
| US9646609B2 (en) | 2014-09-30 | 2017-05-09 | Apple Inc. | Caching apparatus for serving phonetic pronunciations |
| US9668121B2 (en) | 2014-09-30 | 2017-05-30 | Apple Inc. | Social reminders |
| US10552013B2 (en) | 2014-12-02 | 2020-02-04 | Apple Inc. | Data detection |
| US9711141B2 (en) | 2014-12-09 | 2017-07-18 | Apple Inc. | Disambiguating heteronyms in speech synthesis |
| US9865280B2 (en) | 2015-03-06 | 2018-01-09 | Apple Inc. | Structured dictation using intelligent automated assistants |
| US9886953B2 (en) | 2015-03-08 | 2018-02-06 | Apple Inc. | Virtual assistant activation |
| US10567477B2 (en) | 2015-03-08 | 2020-02-18 | Apple Inc. | Virtual assistant continuity |
| US9721566B2 (en) | 2015-03-08 | 2017-08-01 | Apple Inc. | Competing devices responding to voice triggers |
| US9899019B2 (en) | 2015-03-18 | 2018-02-20 | Apple Inc. | Systems and methods for structured stem and suffix language models |
| US9842105B2 (en) | 2015-04-16 | 2017-12-12 | Apple Inc. | Parsimonious continuous-space phrase representations for natural language processing |
| US10083688B2 (en) | 2015-05-27 | 2018-09-25 | Apple Inc. | Device voice control for selecting a displayed affordance |
| US10127220B2 (en) | 2015-06-04 | 2018-11-13 | Apple Inc. | Language identification from short strings |
| US10101822B2 (en) | 2015-06-05 | 2018-10-16 | Apple Inc. | Language input correction |
| US10186254B2 (en) | 2015-06-07 | 2019-01-22 | Apple Inc. | Context-based endpoint detection |
| US11025565B2 (en) | 2015-06-07 | 2021-06-01 | Apple Inc. | Personalized prediction of responses for instant messaging |
| US10255907B2 (en) | 2015-06-07 | 2019-04-09 | Apple Inc. | Automatic accent detection using acoustic models |
| US10747498B2 (en) | 2015-09-08 | 2020-08-18 | Apple Inc. | Zero latency digital assistant |
| US10671428B2 (en) | 2015-09-08 | 2020-06-02 | Apple Inc. | Distributed personal assistant |
| US9697820B2 (en) | 2015-09-24 | 2017-07-04 | Apple Inc. | Unit-selection text-to-speech synthesis using concatenation-sensitive neural networks |
| US10366158B2 (en) | 2015-09-29 | 2019-07-30 | Apple Inc. | Efficient word encoding for recurrent neural network language models |
| US11010550B2 (en) | 2015-09-29 | 2021-05-18 | Apple Inc. | Unified language modeling framework for word prediction, auto-completion and auto-correction |
| US11587559B2 (en) | 2015-09-30 | 2023-02-21 | Apple Inc. | Intelligent device identification |
| US10691473B2 (en) | 2015-11-06 | 2020-06-23 | Apple Inc. | Intelligent automated assistant in a messaging environment |
| US10049668B2 (en) | 2015-12-02 | 2018-08-14 | Apple Inc. | Applying neural network language models to weighted finite state transducers for automatic speech recognition |
| US10223066B2 (en) | 2015-12-23 | 2019-03-05 | Apple Inc. | Proactive assistance based on dialog communication between devices |
| US9836669B2 (en) | 2016-02-22 | 2017-12-05 | International Business Machines Corporation | Generating a reference digital image based on an indicated time frame and searching for other images using the reference digital image |
| US10446143B2 (en) | 2016-03-14 | 2019-10-15 | Apple Inc. | Identification of voice inputs providing credentials |
| US9934775B2 (en) | 2016-05-26 | 2018-04-03 | Apple Inc. | Unit-selection text-to-speech synthesis based on predicted concatenation parameters |
| US9972304B2 (en) | 2016-06-03 | 2018-05-15 | Apple Inc. | Privacy preserving distributed evaluation framework for embedded personalized systems |
| US10249300B2 (en) | 2016-06-06 | 2019-04-02 | Apple Inc. | Intelligent list reading |
| US10049663B2 (en) | 2016-06-08 | 2018-08-14 | Apple, Inc. | Intelligent automated assistant for media exploration |
| DK179309B1 (en) | 2016-06-09 | 2018-04-23 | Apple Inc | Intelligent automated assistant in a home environment |
| US10509862B2 (en) | 2016-06-10 | 2019-12-17 | Apple Inc. | Dynamic phrase expansion of language input |
| US10067938B2 (en) | 2016-06-10 | 2018-09-04 | Apple Inc. | Multilingual word prediction |
| US10586535B2 (en) | 2016-06-10 | 2020-03-10 | Apple Inc. | Intelligent digital assistant in a multi-tasking environment |
| US10490187B2 (en) | 2016-06-10 | 2019-11-26 | Apple Inc. | Digital assistant providing automated status report |
| US10192552B2 (en) | 2016-06-10 | 2019-01-29 | Apple Inc. | Digital assistant providing whispered speech |
| DK179415B1 (en) | 2016-06-11 | 2018-06-14 | Apple Inc | Intelligent device arbitration and control |
| DK179049B1 (en) | 2016-06-11 | 2017-09-18 | Apple Inc | Data driven natural language event detection and classification |
| DK201670540A1 (en) | 2016-06-11 | 2018-01-08 | Apple Inc | Application integration with a digital assistant |
| DK179343B1 (en) | 2016-06-11 | 2018-05-14 | Apple Inc | Intelligent task discovery |
| US10593346B2 (en) | 2016-12-22 | 2020-03-17 | Apple Inc. | Rank-reduced token representation for automatic speech recognition |
| US10417269B2 (en) * | 2017-03-13 | 2019-09-17 | Lexisnexis, A Division Of Reed Elsevier Inc. | Systems and methods for verbatim-text mining |
| DK179745B1 (en) | 2017-05-12 | 2019-05-01 | Apple Inc. | SYNCHRONIZATION AND TASK DELEGATION OF A DIGITAL ASSISTANT |
| DK201770431A1 (en) | 2017-05-15 | 2018-12-20 | Apple Inc. | Optimizing dialogue policy decisions for digital assistants using implicit feedback |
| JP6931442B2 (ja) * | 2017-05-16 | 2021-09-08 | 富士通株式会社 | 符号化プログラム、インデックス生成プログラム、検索プログラム、符号化装置、インデックス生成装置、検索装置、符号化方法、インデックス生成方法および検索方法 |
| US10606895B2 (en) * | 2017-07-12 | 2020-03-31 | Microsoft Technology Licensing, Llc | Multiple entity aware typeahead in searches |
| US11133090B2 (en) * | 2017-09-22 | 2021-09-28 | Cerner Innovation, Inc. | Semantic search for a health information exchange |
| CN108984666B (zh) * | 2018-06-29 | 2022-05-13 | 阿里巴巴集团控股有限公司 | 数据处理方法、数据处理装置和服务器 |
| US11145296B1 (en) * | 2019-03-25 | 2021-10-12 | Amazon Technologies, Inc. | Language and grammar model adaptation |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4672571A (en) * | 1984-10-24 | 1987-06-09 | International Business Machines Corporation | Compound word suitability for spelling verification |
| US4701851A (en) * | 1984-10-24 | 1987-10-20 | International Business Machines Corporation | Compound word spelling verification |
| JPH0625901B2 (ja) * | 1986-08-08 | 1994-04-06 | 三輪 博秀 | 電子単一言語辞典及び電子複数言語間辞典 |
| US4777617A (en) * | 1987-03-12 | 1988-10-11 | International Business Machines Corporation | Method for verifying spelling of compound words |
| US4873634A (en) * | 1987-03-27 | 1989-10-10 | International Business Machines Corporation | Spelling assistance method for compound words |
| JP2702927B2 (ja) * | 1987-06-15 | 1998-01-26 | 株式会社日立製作所 | 文字列検索装置 |
| EP0468402B1 (en) * | 1990-07-23 | 2000-05-10 | Hitachi, Ltd. | Character string retrieving system and method |
| US5323316A (en) * | 1991-02-01 | 1994-06-21 | Wang Laboratories, Inc. | Morphological analyzer |
-
1992
- 1992-07-20 US US07/916,576 patent/US5625554A/en not_active Expired - Lifetime
-
1993
- 1993-06-30 JP JP15980493A patent/JP3196868B2/ja not_active Expired - Fee Related
- 1993-07-19 DE DE69331209T patent/DE69331209T2/de not_active Expired - Lifetime
- 1993-07-19 EP EP93305626A patent/EP0583083B1/en not_active Expired - Lifetime
- 1993-07-19 ES ES93305626T patent/ES2168267T3/es not_active Expired - Lifetime
-
1994
- 1994-06-08 US US08/255,504 patent/US5594641A/en not_active Expired - Lifetime
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0785047A (ja) * | 1993-08-02 | 1995-03-31 | Xerox Corp | コンパクトにエンコードされて記憶されたストリングの組を有する製品 |
Also Published As
| Publication number | Publication date |
|---|---|
| US5594641A (en) | 1997-01-14 |
| EP0583083A2 (en) | 1994-02-16 |
| EP0583083A3 (en) | 1994-09-07 |
| ES2168267T3 (es) | 2002-06-16 |
| US5625554A (en) | 1997-04-29 |
| JP3196868B2 (ja) | 2001-08-06 |
| DE69331209D1 (de) | 2002-01-10 |
| DE69331209T2 (de) | 2002-05-23 |
| EP0583083B1 (en) | 2001-11-28 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3196868B2 (ja) | テキストをインデックス及び検索するための関連ワード形態の限定状態トランスジューサ | |
| US5724593A (en) | Machine assisted translation tools | |
| CN100511215C (zh) | 多语种翻译存储器和翻译方法 | |
| EP0637805A2 (en) | Context-sensitive method of finding information about a word in an electronic dictionary | |
| JPH0447364A (ja) | 自然言語解析装置及び方法並びに自然言語解析用知識ベース構築方法 | |
| Mahmood et al. | Query based information retrieval and knowledge extraction using Hadith datasets | |
| US4811400A (en) | Method for transforming symbolic data | |
| CN101667099B (zh) | 一种连笔键盘文字输入的方法和设备 | |
| HIRPSSA et al. | POS Tagging for Amharic Text: A Machine Learning Approach. | |
| KR100288144B1 (ko) | 한글로 표기된 외래어 코드화 방법 및 그를 이용한 검색 방법 | |
| JP3617096B2 (ja) | 関係表現抽出装置および関係表現検索装置、関係表現抽出方法、関係表現検索方法 | |
| Nunsanga et al. | Part-of-speech tagging for Mizo language using conditional random field | |
| JP5169456B2 (ja) | 文書検索システム、文書検索方法および文書検索プログラム | |
| JP2005025555A (ja) | シソーラス構築システム、シソーラス構築方法、この方法を実行するプログラム、およびこのプログラムを記憶した記憶媒体 | |
| JP2004206659A (ja) | 読み情報決定方法及び装置及びプログラム | |
| JP3847801B2 (ja) | 文字処理装置及びその処理方法 | |
| JPS63228326A (ja) | キ−ワ−ド自動抽出方式 | |
| Kadam | Develop a Marathi Lemmatizer for Common Nouns and Simple Tenses of Verbs | |
| Kefena et al. | POS Tagging for Amharic: A Machine Learning Approach | |
| JPH0271362A (ja) | 仮名漢字変換装置 | |
| JP3048793B2 (ja) | 文字変換装置 | |
| JPH03210659A (ja) | 複合語表現範囲決定方法および装置 | |
| JPH07210571A (ja) | 単語検索処理装置及び単語検索処理方法 | |
| JPH01258069A (ja) | 日本語文字列の形態素解析方式 | |
| WO2018228101A1 (zh) | 基于汉语含义的汉语编码方法及系统和介质设备 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20010507 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080608 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090608 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100608 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110608 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110608 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120608 Year of fee payment: 11 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130608 Year of fee payment: 12 |
|
| LAPS | Cancellation because of no payment of annual fees |