(57)【特許請求の範囲】
【請求項１】
単語境界マーカーのない言語で記述されたテキストに対して単語列を選択するための方法であって、
前記テキストを複数の単語列に分割することと、
第１の単語列中の単語分割単位の後にある単語境界の位置が、第２の単語列中の単語分割単位の後にある前記単語境界の前記位置と同じであるとき、前記単語境界を共通の単語境界であると判定することと、
前記共通の単語境界の前にある前記第１の単語列の部分または前記共通の単語境界の前にある前記第２の単語列の部分のうちの一方から、最適な単語列を選択することであって、前記共通の単語境界の前にある前記第１の単語列の部分内の少なくとも１つの単語分割単位は、前記共通の単語境界の前にある前記第２の単語列の部分内の少なくとも１つの単語分割単位と異なる、ことと、
を含む、方法。
【請求項２】
前記共通の単語境界の前にある前記第１の単語列の部分または前記共通の単語境界の前にある前記第２の単語列の部分のうちのいずれかを、最適な単語列として選択することは、
前記第１および第２の単語列中の前記共通の境界の後に、さらなる共通の境界が存在しない場合に、別の最適な単語列のさらなる選択を実施しないことと、
そうでなければ、前記第１および第２の単語列の残存部分に対して別の最適な単語列の選択を継続することと、
を含む、請求項１に記載の方法。
【請求項３】
前記テキストを複数の単語列に分割することは、
単語分割単位を取得するために、前記テキストを辞書内の用語に対して適合させることと、
少なくとも２つの前記単語分割単位を付加して、第３の単語列を生成することと、
前記単語分割単位を前記第３の単語列に付加することによって、前記第３の単語列を異なる単語列に拡張することと、
を含む、請求項１に記載の方法。
【請求項４】
前記テキストの単語文字列を辞書内の用語に対して適合させることは、
前記テキストにおいて、前記辞書内の用語と一致する用語を発見することと、
前記一致する用語が発見された場合、前記テキストにおける前記一致した用語の次の単語から開始する次の前記発見を実施することと、
そうでなければ、不適合の単語の最初の単語から開始する次の前記発見を実施することと、
を含む、請求項３に記載の方法。
【請求項５】
前記単語分割単位を第３の単語列に付加することは、
前記第３の単語列の全ての単語分割単位の後に、新しい単語分割単位が現れる場合、前記新しい単語分割単位を前記第３の単語列に付加することと、
前記第３の単語列の単語列の全ての単語分割単位の後に、新しい単語分割単位が現れない場合、前記新しい単語分割単位を前記第３の単語列に付加しないことと、
を含む、請求項３に記載の方法。
【請求項６】
単語境界を共通の単語境界であると判定することは、
前記異なる単語列の中で、単語境界が、前記複数の単語分割単位のそれぞれの最後の単語の後にある場合、前記単語境界を、前記異なる単語列に対して共通の単語境界であると判定すること、
を含む、請求項３に記載の方法。
【請求項７】
前記最適な単語列を選択すると、１つ以上の単語列は、メモリに維持される、請求項１に記載の方法。
【請求項８】
選択された最適な単語列に基づいて、検索を実施すること、をさらに含む、請求項１に記載の方法。
【請求項９】
前記最適な単語列を選択することは、統計的アルゴリズムを使用して、前記最適な単語列を選択することを含む、請求項１に記載の方法。
【請求項１０】
前記最適な単語列を選択することは、最大適合アルゴリズムを使用して、前記最適な単語列を選択することを含む、請求項１に記載の方法。
【請求項１１】
単語境界マーカーのない言語で記述されたテキストに対して単語列を選択するためのコンピュータで実行されるシステムであって、
前記テキストを複数の単語列に分割するように構成された単語分割処理モジュールと、
第１の単語列中の単語分割単位の後にある単語境界の位置が、第２の単語列中の単語分割単位の後にある前記単語境界の前記位置と同じであるとき、前記単語境界を共通の単語境界であると判定するように構成される、単語境界判定モジュールと、
前記共通の単語境界の前にある前記第１の単語列の部分または前記共通の単語境界の前にある前記第２の単語列の部分のうちの一方から、最適な単語列を選択するように構成される単語列選択モジュールであって、前記共通の単語境界の前にある前記第１の単語列の部分内の少なくとも１つの単語分割単位は、前記共通の単語境界の前にある前記第２の単語列の部分内の少なくとも１つの単語分割単位と異なる、単語列選択モジュールと、
を備える、システム。
【請求項１２】
前記単語列選択は、
前記第１および第２の単語列中の前記共通の境界の後に、さらなる共通の境界が存在しない場合に、別の最適な単語列のさらなる選択を実施しないように、
そうでなければ、前記第１および第２の単語列の残存部分に対して別の最適な単語列の選択を継続するように、
さらに構成される、請求項１１に記載のシステム。
【請求項１３】
前記単語分割処理モジュールは、
単語分割単位を取得するために、前記テキストを辞書内の用語に対して適合させ、
少なくとも２つの前記単語分割単位を付加して、第３の単語列を生成し、
前記単語分割単位を前記第３の単語列に付加することによって、前記第３の単語列を異なる単語列に拡張するように、
さらに構成される、請求項１１に記載のシステム。
【請求項１４】
前記単語分割処理モジュールは、
前記テキストにおいて、前記辞書内の用語と一致する用語を発見し、
前記一致する用語が発見された場合、前記テキストにおける前記一致した用語の次の単語から開始する次の前記発見を実施し、
そうでなければ、不適合の単語の最初の単語から開始する次の前記発見を実施するように、
さらに構成される、請求項１３に記載のシステム。
【請求項１５】
前記単語分割処理モジュールは、
前記第３の単語列の全ての単語分割単位の後に、新しい単語分割単位が現れる場合、前記新しい単語分割単位を前記第３の単語列に付加し、
前記第３の単語列の全ての単語分割単位の後に、新しい単語分割単位が現れない場合、前記新しい単語分割単位を前記第３の単語列に付加しないように、
さらに構成される、請求項１３に記載のシステム。
【請求項１６】
前記単語境界判定モジュールは、
前記異なる単語列の中で、単語境界が、前記複数の単語分割単位のそれぞれの最後の単語の後にある場合、前記単語境界を、前記異なる単語列に対する共通の単語境界であると判定するように、
さらに構成される、請求項１３に記載のシステム。
【請求項１７】
前記単語列選択モジュールは、前記最適な単語列を選択すると、１つ以上の単語列を保持するようにさらに構成される、請求項１１に記載のシステム。
【請求項１８】
選択された最適な単語列に基づいて、検索を実施するように構成される、検索エンジンモジュールをさらに備える、
請求項１１に記載のシステム。
【請求項１９】
前記単語列選択モジュールは、統計的アルゴリズムを使用して、前記最適な単語列を選択する、請求項１１に記載のシステム。
【請求項２０】
前記単語列選択モジュールは、最大適合アルゴリズムを使用して、前記最適な単語列を選択する、請求項１１に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連特許）
本出願は、「ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＯＦ  ＳＥＬＥＣＴＩＮＧ  ＷＯＲＤ  ＳＥＱＵＥＮＣＥ  ＦＯＲ  ＴＥＸＴ  ＷＲＩＴＴＥＮ  ＩＮ  ＬＡＮＧＵＡＧＥ  ＷＩＴＨＯＵＴ  ＷＯＲＤ  ＢＯＵＮＤＡＲＹ  ＭＡＲＫＥＲＳ」という発明の名称で、２００８年１２月３１日に出願された中国特許出願第２００８１０１９２９３４．４号の優先権の利益を主張するものであり、参照によりその全体が本願明細書に組み込まれる。
【０００２】
本開示は、概して、テキスト情報処理の分野に関し、より具体的には、単語境界マーカーのない言語で記述されたテキストに対して単語列を選択することに関する。
【背景技術】
【０００３】
世界中の言語およびテキストの中で、英語およびドイツ語等のある種類の言語は、単語境界マーカーを有し、概して、単語間を分断するために、境界マーカーとしてスペースを使用する。別の種類の言語には、文中の単語間に区切り記号が存在しない、中国語、日本語および韓国語等の単語境界マーカーのない言語が含まれる。コンピュータ技術が発達するにつれて、検索エンジン、テキスト検索および機械翻訳等のアプリケーションは全て、テキスト処理の課題を伴う。従って、文を単語および語句に分割する方法が主要な懸念事項となっている。
【０００４】
以下の説明は、中国語以外の同様の言語にも当てはまるが、説明を簡単にするため、中国語を説明の例として使用する。中国語単語分割技術は、数十年前からある。早くも１９８０年代には、人々は、コンピュータを使用して中国語の用語を自動的に分割する方法を調査し始めていた。単語分割は、用語から成る文から、各意味のある用語を識別する処理を言う。
【０００５】
中国語単語分割の一例として、単語適合がある。中国語単語の所与の文字列中の用語は、辞書（またはレキシコン）内の対応する用語に適合される。所与の用語に対して辞書内で適合が発見できない場合、用語は、個々の単語、つまり中国語文字にさらに分割される。従って、単純な単語分割を完了することができ、その後、単語列を形成することができる。
【０００６】
0005540015.tif 000002
【０００７】
0005540015.tif 000003
【０００８】
ＭＭＳＥＧとして既知の最大適合方法は、最大用語適合および最大平均語長等の多数の規則に基づいて、最適な単語列を選択するための簡易アルゴリズムである。別の比較的より洗練された方法は、１９９０年代にＴｓｉｎｇｈｕａ  ＵｎｉｖｅｒｓｉｔｙのＤｒ．Ｊｉｎ  Ｇｕｏによって提唱された統計的言語モデルである。
【０００９】
0005540015.tif 000004
【００１０】
しかしながら、単語分割のこの簡単かつ効果的な手法は、比較的深刻な問題を有する。つまり、文が非常に長い場合、より多様な単語列が存在する。可能な全ての単語列を網羅的に一覧し、各可能性において文の確率を計算すると、計算負荷は極めて大きくなる場合がある。統計的モデルのみこの問題に直面しているのではなく、最適な単語列を選択するための他の方法も、非常に大きな計算負荷の問題に直面している。
【発明の概要】
【００１１】
既存の技術において多様性の高い単語列が存在する場合、最適な単語列を選択する時に、非常に大きな計算負荷を有する問題を解決するため、本開示の例示的な実施形態は、単語境界マーカーのない言語で記述されたテキストに対して単語列を選択するためのコンピュータで実施される方法を提供する。
【００１２】
方法は、異なる単語列を取得するために、テキストのセグメントを分割することであって、各単語列は、他の単語列に含まれる単語分割単位と異なる少なくとも１つの単語分割単位を含む、ことと、ある単語列中の単語分割単位の後にある単語境界の位置が、別の列中の単語分割単位の後にある単語境界の位置と同じであるかどうかを判定し、かつ同じ位置にある単語境界を、単語列に対する共通の単語境界と見なすことと、共通の単語境界の前にある単語列の部分に対して、最適な単語列の選択を実施することであって、共通の単語境界の前にある単語列の部分は、共通の単語境界の前にある他の単語列の部分内の単語分割単位と異なる少なくとも１つの単語分割単位を別々に含む、こととを含む。
【００１３】
本開示の例示的な実施形態は、単語境界マーカーのない言語で記述されたテキストに対して単語列を選択するためのコンピュータ実行システムをさらに提供し、システムは、異なる単語列を取得するために、テキストのセグメントを分割するために使用される単語分割処理モジュールであって、各単語列は、他の単語列中の単語分割単位と異なる少なくとも１つの単語分割単位を別々に含む、単語分割処理モジュールと、ある単語列中の単語分割単位の後にある単語境界の位置が、別の列中の単語分割単位の後にある単語境界の位置と同じであるかどうか判定し、かつ、同じ位置にある単語境界を、単語列に対する共通の単語境界であると見なすために使用される、単語境界判定モジュールと、共通の単語境界の前にある単語列の部分に対して、最適な単語列の選択を実施するために使用される単語列選択モジュールであって、共通の単語境界の前にある単語列の部分は、共通の単語境界の前にある他の単語列の部分内の単語分割単位と異なる少なくとも１つの単語分割単位を別々に含む、単語列選択モジュールと、を備える。
【００１４】
本開示に提供する具体的な実施スキームで説明するように、単語境界は、文間を分断する句読点で通常生成されるため、より短い独立単位を容易に取得することができる。多数の曖昧性を有する文（例えば、曖昧性の３つの原因を有するために作成される３つの共通の単語境界を有する文）の場合、それぞれの計算負荷は低減する。辞書内の用語が、句読点を含む場合、単語境界は句読点で生成されていない場合がある、従って、間違った単語分割を回避することができる。さらに、結合の要求は容易に満たされる。単語列は、単語分割単位に対して、同じ境界が右側に存在する限り、結合されてもよい。結合の要求はより正確である。単語境界によって分割される最小の単位は独立しているため、全ての単語列に対して最小単位間で結合が実施される。これは合理的であるばかりでなく、あらゆる正しい可能性がある単語分割を無視することなく、妥当である。
【図面の簡単な説明】
【００１５】
【図１】一実施形態に従う工程のフローチャートである。
【図２】一実施形態に従う工程の構造図である。
【発明を実施するための形態】
【００１６】
0005540015.tif 000005
【００１７】
0005540015.tif 000006
【００１８】
明らかに、文が、例えば、単語を形成することができない、例えばコンマ等の句読点を有する場合、全ての単語列中で、このコンマの左側および右側に単語境界が存在しなければならない。
【００１９】
0005540015.tif 000007
【００２０】
従って、共通の単語境界を使用して単語列を結合する操作は、以下の通りに定義することができる。単語分割の過程で、共通の単語境界が現れる場合、最適な単語列を選択するために、単語境界の前にある全ての単語列が結合され、一方で、この単語境界の後では、単語分割が継続する。
【００２１】
図１は、単語境界マーカーのない言語で記述されたテキストに対して単語列を選択するためのコンピュータで実行される工程１００を示す。工程１００は、以下のアクションを含む。  
１０１で、テキストＴのセグメントが入力される。  
１０２で、単語分割単位を取得するために、入力されたテキストＴ内の適合した用語および不適合の用語が、単語適合を通じて判定される。  
１０３で、単語適合後に取得された単語分割単位が、単語列に付加される。  
１０４で、種々の単語列を取得するために、曖昧性が存在する位置で、単語列が拡張される。  
１０５で、共通の境界を通して種々の単語列が結合され、最適な単語列が選択される。
例示を目的として、下記に検索エンジンの例を用いて工程１００を説明する。
【００２２】
以下の記述は、テキスト検索および機械翻訳等のアプリケーションにも当てはまる。
【００２３】
１０１で、入力されたテキストＴは、検索が検索エンジンによって実施される前に、インターフェースを通じて受信される。テキストＴのセグメントは、Ｓ１Ｓ２Ｓ３Ｓ４Ｓ５Ｓ６Ｓ７を含んでもよく、Ｓ１〜Ｓ７のそれぞれは、別々に１つの単語を表す。
【００２４】
１０２で、検索エンジンの単語分割処理モジュールは、左から右にテキストＴのセグメントを一度走査し（通常のテキスト中では、単語は、典型的に左から右に表されるため、本明細書における走査は、左から右になされる。テキスト中で単語が右から左に表される場合、走査はテキスト中で右から左になされる）、そして、それと（多数の事前に記憶された単語グループを有する）レキシコン内の単語グループを比較する。用語に対応するレキシコン内の単語グループが見つかった場合、用語は適合する。例えば、単語適合を通じて、単語分割処理モジュールは、不適合の用語として“Ｓ１Ｓ２”を、適合した用語として“Ｓ３Ｓ４Ｓ５Ｓ６”を、適合した用語として“Ｓ３Ｓ４”および“Ｓ５Ｓ６”を、そして不適合の用語として“Ｓ７”を取得する。ここで、適合規則とは、前回の単語適合において取得された適合した用語の最初の単語の後、あるいは、代替的に、前回の単語適合において取得された不適合の単語の後、その後の単語適合を実施することを言う。一実施形態において、最初の単語適合の後に、適合した用語“Ｓ１Ｓ２”が単語分割単位として取得される場合（最初の単語適合は、テキストＴのセグメント中の最初の単語“Ｓ１”から始まる）、次いで、新しい単語適合は、“Ｓ１”の後から始まる。別の実施形態において、最初の単語適合の後に、１つの単語“Ｓ１”が単語分割単位として取得される場合、新しい単語適合は、“Ｓ１”の後から始まる。“Ｓ２Ｓ３”等の用語が、テキストＴの“Ｓ１”の後に適合される場合、その後の手順において第３の単語列が存在する場合がある。
【００２５】
単語適合の工程の概要を以下に記述する。  
１．単語分割処理モジュールは、レキシコン（または辞書）から適合した用語を一語ずつ発見する。  
２．単語分割処理モジュールが、適合した用語を発見した場合、適合した単語の後の最初の単語からその後の単語適合が始まる。単語分割処理モジュールによって、適合した用語が発見されない場合、その後の単語適合は、特定の対象単語の後から始まる。  
３．単語分割処理モジュールは、文の最初から文の最後まで、用語適合の上記２つのステップを繰り返す。
【００２６】
種々の単語分割単位を取得するために、単語分割に対して辞書／レキシコンを引く上記の方法は、一実施形態に従う好適なスキームにすぎない。本開示は、これに限定されるものではない。例えば、種々の単語分割単位を取得するために、インターネット検索エンジンを使用して、テキストＴの入力されたセグメントの検索を実施してもよい。
【００２７】
１０３で、単語分割処理モジュールは、まず、単語分割単位の追加のために、予備の単語列集合を確立する。予備の単語列集合は、最初は、単語分割単位のない空の集合である。
【００２８】
１０２の後、単語分割処理モジュールは、取得した単語分割単位を予備の単語列集合に追加して、これまでに取得した単語列を追跡する。
【００２９】
この追加工程中、単語分割処理モジュールが、適合した用語は、単語列の全ての適合した用語の後に位置することを発見すると、単語分割処理モジュールは、新しく発見した適合した用語をその単語列に追加する。単語分割処理モジュールが、適合した用語は、いずれか一つの単語列の全ての適合した用語の後に現れないことを発見すると、単語分割処理モジュールは、新しい単語列を作成する。例えば、単語分割処理モジュールは、まず、単語分割単位“Ｓ１Ｓ２”を予備の単語列集合に追加して、単語列“Ｓ１Ｓ２”を取得する。単語分割単位“Ｓ３Ｓ４Ｓ５Ｓ６”は、単語分割単位“Ｓ１Ｓ２”の後に位置付けられるため、“Ｓ３Ｓ４Ｓ５Ｓ６”は、その単語列に付加され、単語列、“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５Ｓ６”が取得される。さらに、単語分割単位“Ｓ３Ｓ４”は、“Ｓ１Ｓ２”の後に位置付けられるため、“Ｓ３Ｓ４”は、単語列“Ｓ１Ｓ２”に付加されてもよい。しかしながら、“Ｓ３Ｓ４”は、単語分割単位“Ｓ３Ｓ４Ｓ５Ｓ６”の後には位置付けられないため、“Ｓ３Ｓ４”を、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５Ｓ６”に付加することはできない。従って、単語分割処理モジュールは、新しい単語列：“Ｓ１Ｓ２−Ｓ３Ｓ４”を作成する。
【００３０】
一実施形態において、単語分割単位を付加する規則は、以下の通りである。  
１．単語分割処理モジュールが、新しい単語分割単位は、単語列の全ての単語分割単位の後に現れることを発見すると、この単語分割単位は、その単語列に付加される。  
２．単語分割処理モジュールが、新しい単語分割単位は、いずれか一つの単語列の全ての単語分割単位の後に現れないことを発見すると、新しい単語列には、この新しい単語分割単位に追加される。
【００３１】
別の実施形態において、複数の単語列が存在する場合に、単語分割単位は追加される。単語分割処理モジュールが、例えば、２つの単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５Ｓ６”および“Ｓ１Ｓ２−Ｓ３Ｓ４”を取得した後、単語分割処理モジュールは、単語分割単位“Ｓ５Ｓ６”を単語列“Ｓ１Ｓ２−Ｓ３Ｓ４”に付加して、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４−Ｓ５Ｓ６”を取得する。
【００３２】
１０４で、単語列を拡張する手順中、単語分割処理モジュールが、新しい単語分割単位を既存の単語列に付加できない状況においてのみならず、複数の単語分割単位が同じ位置で作成され、その時に単語列から分岐が生成される状況においても、単語列の数は増加する。
【００３３】
上記の例で説明するように、単語列“Ｓ１Ｓ２”は、元の単語列である。単語分割単位“Ｓ３Ｓ４”および“Ｓ３Ｓ４Ｓ５Ｓ６”は、同じ位置から生成された新しい単語分割単位である。これらの２つの新しい単語分割単位は、元の単語列“Ｓ１Ｓ２”から別々に拡張され、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４”および“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５Ｓ６”がそれぞれ得られる。単語分割処理モジュールはまた、単語分割単位“Ｓ５Ｓ６”を“Ｓ１Ｓ２−Ｓ３Ｓ４”に付加して、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４−Ｓ５Ｓ６”を取得する。
【００３４】
実際には、上記の手順は、単語分割処理モジュールによる、新しい単語分割単位の元の単語列への追加工程を言う。違いの１つは以下の通りである。一度に複数の  単語分割単位が追加される場合、単語分割処理モジュールは、元の単語列を複製する。
【００３５】
１０５で単語列を結合する手順中、単語境界判定モジュールは、それぞれの単語列中の“−”を探すことによって、上記単語列のそれぞれにおいて単語境界を判定する。さらに、テキスト全体内の“−”の前で発見される単語の位置に基づいて、単語境界判定モジュールは、その特定の“−”の位置を判定する。一実施形態において、例えば、“−”が、テキスト全体内の第２の単語“Ｓ２”の後に位置付けられている場合、単語境界判定モジュールは、“Ｓ１Ｓ２”の後に位置するこの“−”が、第２の位置にあると判定してもよい。あるいは、単語境界判定モジュールは、“−”が第３の単語“Ｓ３”の前に位置するため、この“−”が第３の位置にあると判定してもよい。単語境界を使用して単語列を結合する規則を後述する。
【００３６】
幾つかの単語列が、同じ位置で単語境界を有することを発見すると、単語境界判定モジュールは、元の文または語句中のその単語境界の前に現れる単語列を結合するように、単語列選択モジュールに通知する。具体的には、ある単語列中の単語分割単位の後にある単語境界の位置が、他の単語列中の特定の単語分割単位の後の単語境界の位置と同じである場合、単語境界判定モジュールは、この単語境界は、これらの単語列に対して共通の単語境界であると判定する。例えば、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４−Ｓ５Ｓ６−Ｓ７”および“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５Ｓ６−Ｓ７”の場合、“Ｓ１Ｓ２”の後に位置する“−”は、これら２つの単語列（両方とも第２の位置にある）に対して共通の単語境界であり、一方で、“Ｓ５Ｓ６”および“Ｓ３Ｓ４Ｓ５Ｓ６”の後に位置する“−”もまた、これらの２つの単語列（両方とも第６の位置にある）に対して共通の単語境界である。
【００３７】
一実施形態において、単語列の拡張後に取得された単語列中の最後の単語分割単位の後にある単語境界の位置が同じであると、単語境界判定モジュールが観察した場合、単語境界判定モジュールは、これらの単語列を結合することができると、単語列選択モジュールに通知する。例えば、１０４で単語列を拡張する過程で、単語列“Ｓ１Ｓ２”は、元の単語列である。単語分割単位“Ｓ５Ｓ６”および“Ｓ３Ｓ４Ｓ５Ｓ６”は、その後のそれぞれの単語境界の位置が同じである、別々に２つの異なる経路に沿った、最後に適合した用語である。次いで、単語境界判定モジュールは、これらの単語列が１つに結合できることを、単語列選択モジュールに通知する。通知を受信すると、単語列選択モジュールは、選択アルゴリズムに基づいて、“Ｓ１Ｓ２−Ｓ３Ｓ４−Ｓ５Ｓ６−Ｓ７”および“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５Ｓ６−Ｓ７”の２つの単語列から、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５Ｓ６−Ｓ７”を最適な単語列として選択してもよい。どの単語列が最適な単語列に特に選択されるかは、単語列選択モジュールによって採用される選択アルゴリズムに依存する。統計的アルゴリズムが使用される場合、種々の単語分割経路の中で、出現確率が最も高いものが選択される。ＭＭＳＥＧ単語分割アルゴリズムが使用される場合、最大の適合した用語を有するものが選択される。１つより多いい最大の適合した用語を有するものが発見された場合、次いで、最大平均長を有するものが選択される。いずれにしても、複数の単語列が依然として最後に残る場合がある。
【００３８】
上述の方法に基づいて、例えば、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５Ｓ６−Ｓ７”が、最適な単語列に選択されてもよい。次いで、検索エンジンは、キーワード検索を行う。
【００３９】
曖昧性の唯一１つの原因を有するテキストＴの上記のセグメントは、本スキームのアイディアを説明するために使用されている。ここで、例示のみを目的として、“Ｓ１Ｓ２Ｓ３Ｓ４Ｓ５”は、“Ｓ１Ｓ２Ｓ３−Ｓ４Ｓ５”および“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５”に分割することができ、一方、“Ｓ６Ｓ７Ｓ８Ｓ９Ｓａ”は、“Ｓ６Ｓ７−Ｓ８Ｓ９Ｓａ”および“Ｓ６Ｓ７Ｓ８−Ｓ９Ｓａ”に分割することができる、２つの曖昧さの原因を有するテキストＴのセグメント“Ｓ１Ｓ２Ｓ３Ｓ４Ｓ５Ｓ６Ｓ７Ｓ８Ｓ９Ｓａ”を使用して、本スキームの例を後述する。
【００４０】
検索エンジンのインターフェースは、テキストＴのセグメント“Ｓ１Ｓ２Ｓ３Ｓ４Ｓ５Ｓ６Ｓ７Ｓ８Ｓ９Ｓａ”を受信する。
【００４１】
単語分割処理モジュールは、左から右にテキストＴのセグメントを一度走査し、そして、それと（多数の事前に記憶された単語グループを有する）レキシコン内の単語グループを比較する。適合した単語分割単位“Ｓ１Ｓ２”および“Ｓ１Ｓ２Ｓ３”は、まず、メモリに事前に記憶された２つの予備の単語列集合に追加され、メモリの２つの異なる記憶域に記憶されている単語列“Ｓ１Ｓ２”および“Ｓ１Ｓ２Ｓ３”が取得される。次いで、単語分割処理モジュールは、単語分割単位“Ｓ３Ｓ４Ｓ５”を単語列“Ｓ１Ｓ２”に付加して、“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５”を取得し、単語分割単位“Ｓ４Ｓ５”を“Ｓ１Ｓ２Ｓ３”に付加して、“Ｓ１Ｓ２Ｓ３−Ｓ４Ｓ５”を取得する。新しく付加した単語分割単位“Ｓ３Ｓ４Ｓ５”および“Ｓ４Ｓ５”の各々の最後の単語が、“Ｓ５”（つまり、テキストＴ中の５番目の単語）であることを発見すると、単語境界判定モジュールは、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５”および“Ｓ１Ｓ２Ｓ３−Ｓ４Ｓ５”が、共通の単語境界を有する単語列であると判定する。単語境界判定モジュールは、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５”および“Ｓ１Ｓ２Ｓ３−Ｓ４Ｓ５”を結合するように単語列選択モジュールに通知する。単語列選択モジュールは、ＭＭＳＥＧ単語分割アルゴリズム（または統計的アルゴリズム）を使用して、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５”および“Ｓ１Ｓ２Ｓ３−Ｓ４Ｓ５”から単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５”を選択する。さらに、単語列“Ｓ１Ｓ２Ｓ３−Ｓ４Ｓ５”を記憶するメモリ領域は、その時点では空である。単語分割単位“Ｓ６Ｓ７”および“Ｓ６Ｓ７Ｓ８”を適合次第、単語分割処理モジュールは、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５”を複製する。２つの等価単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５”は、メモリの２つの異なる記憶域に別々に記憶される。単語分割単位“Ｓ６Ｓ７”および“Ｓ６Ｓ７Ｓ８”を、２つの等価単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５”に別々に付加した後、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７”および“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７Ｓ８”が取得される。単語分割処理モジュールは、単語分割単位“Ｓ８Ｓ９Ｓａ”の適合を取得し、この単語分割単位“Ｓ８Ｓ９Ｓａ”を単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７”に付加して、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７−Ｓ８Ｓ９Ｓａ”を取得する。次いで、単語分割処理モジュールは、単語分割単位“Ｓ９Ｓａ”の適合を取得し、この単語分割単位“Ｓ９Ｓａ”を単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７Ｓ８”に付加して、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７Ｓ８−Ｓ９Ｓａ”を取得する。新しく追加された単語分割単位“Ｓ８Ｓ９Ｓａ”および“Ｓ９Ｓａ”のそれぞれの最後の単語が、“Ｓａ”（つまり、テキストＴ中の１０番目の単語）であることを発見すると、単語境界判定モジュールは、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７−Ｓ８Ｓ９Ｓａ”および“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７Ｓ８−Ｓ９Ｓａ”が共通の単語境界を有する単語列であると判定する。単語境界判定モジュールは、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７−Ｓ８Ｓ９Ｓａ”および“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７Ｓ８−Ｓ９Ｓａ”を結合するように単語列選択モジュールに通知する。単語列選択モジュールは、ＭＭＳＥＧ単語分割アルゴリズム（または統計的アルゴリズム）を使用して、２つの単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７−Ｓ８Ｓ９Ｓａ”および“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７Ｓ８−Ｓ９Ｓａ”から単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７−Ｓ８Ｓ９Ｓａ”を選択する。さらに、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７Ｓ８−Ｓ９Ｓａ”を記憶するメモリ領域は、その時点では空である。
【００４２】
0005540015.tif 000008
【００４３】
一実施形態において、単語列中で取得される最後の単語分割単位の最後の単語の位置が同じである場合、これらの単語列は、即座に結合されない場合がある。例えば、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７−Ｓ８Ｓ９Ｓａ”および“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７Ｓ８−Ｓ９Ｓａ”の場合、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５”および“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５”に対して、これらの単語列が取得される時に、単語列結合は実施されない。むしろ、単語列結合は、単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７−Ｓ８Ｓ９Ｓａ”および“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７Ｓ８−Ｓ９Ｓａ”に対して、これらの単語列が取得される時に実施される。
【００４４】
一実施形態において、共通の単語境界が取得された単語列中に現れる場合、共通の単語境界の後の単語列が結合される場合がある。以下の例は、説明の例として“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７−Ｓ８Ｓ９Ｓａ”および“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７Ｓ８−Ｓ９Ｓａ”を使用する。単語列“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７−Ｓ８Ｓ９Ｓａ”および“Ｓ１Ｓ２−Ｓ３Ｓ４Ｓ５−Ｓ６Ｓ７Ｓ８−Ｓ９Ｓａ”において共通の単語境界を取得すると、共通の単語境界の後の単語列“Ｓ６Ｓ７−Ｓ８Ｓ９Ｓａ”および“Ｓ６Ｓ７Ｓ８−Ｓ９Ｓａ”に対して、単語列結合が実施される。
【００４５】
共通の単語境界を使用して単語列を結合する利点がここに再考される。単語境界は、文間を分断するように機能する句読点で通常生成されるため、より短い独立単位が容易に取得でき、従って単語分割の計算負荷も低減する場合がある。辞書内の用語が、句読点を含む場合、単語境界は句読点で生成されない場合があるため、従って、間違った単語分割を回避することができる。さらに、結合のいかなる要求も容易に満たすことができる。単語列は、同じ境界が対象の単語分割単位の右側に存在する限り、結合される場合がある。
【００４６】
単語境界によって分割された最小単位は独立しているため、結合は、全ての単語列に対して最小単位間で実施される。これは合理的であるばかりでなく、あらゆる正しい可能性がある単語分割を無視することなく、妥当である。
【００４７】
図２は、単語境界マーカーのない言語で記述されたテキストに対して単語列を選択するためのコンピュータで実行されるシステム２００を示す。システム２００は、異なる単語列を取得するために、テキストのセグメントを分割する単語分割処理モジュール２０１であって、各単語列は、他の単語列中の単語分割単位と異なる少なくとも１つの単語分割単位を別個に含む、単語分割処理モジュール２０１と、ある単語列中の単語分割単位の後の単語境界の位置が、別の列中の単語分割単位の後の単語境界の位置と同じかどうか判定し、かつ同じ位置の単語境界を、単語列に対して共通の単語境界であると認識する、単語境界判定モジュール２０２と、共通の単語境界の前にある単語列の部分に対して、最適な単語列の選択を実施する単語列選択モジュール２０３であって、該共通の単語境界の前にある単語列の部分は、共通の単語境界の前にある他の単語列の部分内の単語分割単位と異なる少なくとも１つの単語分割単位を別々に含む、単語列選択モジュール２０３と、を備える。
【００４８】
一実施形態において、単語列選択モジュール２０３は、共通の境界の後にさらなる共通境界が存在しない場合に、最適な単語列のさらなる選択を実施しないようにさらに構成される。そうでなければ、単語列選択モジュール２０３は、共通の単語境界の前にある単語列の部分に対して最適な単語列の選択を実施した後に、最適な単語列の選択を継続する。
【００４９】
一実施形態において、単語分割処理モジュール２０１は、単語分割単位を取得するために、テキストのセグメントの単語文字列を辞書内の用語に対して適合させ、単語分割単位を単語列に追加し、そして、単語文字列中に曖昧性が存在し、かつ複数の単語分割単位を追加する必要がある場合に、単語列を異なる単語列に拡張するようにさらに構成される。
【００５０】
一実施形態において、単語分割処理モジュール２０１は、辞書内の適合した用語を一語ずつ発見し、適合した用語が発見された場合、適合した用語の２番目の単語から次の適合を実施するようにさらに構成される。そうでなければ、単語分割処理モジュール２０１は、不適合の単語の最初の単語から次の適合を実施する。
【００５１】
一実施形態において、単語分割処理モジュール２０１は、新しい単語分割単位が、ある単語列の全ての単語分割単位の後に現れる場合に、新しい単語分割単位をある単語列に追加し、新しい単語分割単位がいずれか一つの単語列の全ての単語分割の後に現れない場合、新しい単語列を追加して、全ての既存の単語列を拡張し、かつ新しい単語分割単位を新しい単語列に追加するようにさらに構成される。
【００５２】
一実施形態において、単語境界判定モジュール２０２は、既存の単語列を拡張した後に取得される種々の単語列の中で、取得した新しい単語分割単位の最後の単語が、同じ単語境界を有することを発見すると、単語境界が種々の単語列に対して共通の単語境界であると判定するようにさらに構成される。
【００５３】
一実施形態において、単語列選択モジュール２０３は、最適な単語列の選択を実施した後に、１つ以上の単語列を保持するようにさらに構成される。
【００５４】
一実施形態において、システム２００は、選択された最適な単語列に基づいて、検索を行う検索エンジンモジュールをさらに含む。
【００５５】
説明を簡単にするため、システム２００の種々の構成要素を、機能上種々のモジュールとして別個に記述する。開示されたシステムおよび方法の種々の実施形態の実施において、種々のモジュールの機能は、１つ以上のソフトウェアおよび／またはハードウェアにおいて実施され得ることを理解すべきである。
【００５６】
上述の例示的な実施形態から、当業者は、開示した方法およびシステムが、ソフトウェアおよび汎用ハードウェアプラットフォームを使用して実施されてもよく、またはハードウェアのみを使用して実施できることを、明確に理解することができる。しかしながら、多くの場合では、ソフトウェアおよびハードウェアの組み合わせを使用する前者の実施が好適である。この理解に基づいて、本開示の技術的なスキーム、または既存の技術に寄与する部分は、ＲＯＭ／ＲＡＭ、ディスクおよびドライブ等の記憶媒体に記憶されるソフトウェア製品という形で実施されてもよい。ソフトウェアは、本開示の種々の例示的な実施形態または例示的な実施形態の特定の部分に記載した方法を実行するために、コンピューティングデバイス（例えば、パーソナルコンピュータ、サーバまたはネットワークデバイス）に対する命令を含む。
【００５７】
当然ながら、本開示の精神および範囲から逸脱することなく、多くの異なる方法で、当業者は本開示を変更または修正することができる。従って、本開示は、本開示の特許請求の範囲およびその均等物の範囲に入る全ての修正および変形を包含することが意図される。
【図１】
0005540015.tif 000009
【図２】
0005540015.tif 000010