(57)【特許請求の範囲】
【請求項１】
コンピュータ実装される方法であって、
マップサーチのためにユーザから受信した入力エントリを複数のトークンを含むトークンシーケンスにパーシングするステップであって、各トークンが、前記入力エントリのセグメントを表すタームと、前記タームにアノテートされたタイプとを含む、ステップと、
前記トークンシーケンスの可能な分割位置を決定するステップであって、各可能な分割位置は、ロケーション情報を含む可能なロケーションサブシーケンスと、検索対象を示す可能なクエリサブシーケンスとに、前記トークンシーケンスを分割する、ステップと、
前記可能な分割位置の各々について分割スコアを決定するステップと、
最も高い分割スコアを有する前記可能な分割位置から、ロケーションサブシーケンスおよびクエリサブシーケンスを選択するステップと、
前記ロケーションサブシーケンスによって示されるロケーションに近いロケーションに関連する前記クエリサブシーケンスに応答する情報を検索するステップとを含む、ことを特徴とする方法。
【請求項２】
前記入力エントリを前記トークンシーケンスにパーシングするステップは、
アドレスタイプのトークンとして前記入力エントリ中で単語を特定するために、アドレス関連単語の辞書を使用するステップを含む、ことを特徴とする請求項１に記載の方法。
【請求項３】
前記辞書のアドレス関連単語が、行政区名、道路名、アドレス関連サフィックス、アドレス関連プリフィックス、および番号の、少なくとも1つを含む、ことを特徴とする請求項２に記載の方法。
【請求項４】
「Road」のタイプを伴うトークンと「Number」のタイプを伴うトークンとの間の分割位置を禁止するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記トークンシーケンスの前記可能な分割位置を決定するステップは、
各可能な分割位置について、前記可能な分割位置から生成された２つのトークンサブシーケンスの各々に対して、ロケーション統計スコアおよびクエリ統計スコアを決定するステップと、
前記可能なロケーションサブシーケンスとしてより高いロケーション統計スコアを有する前記トークンサブシーケンスを、かつ前記可能なクエリサブシーケンスとして他のトークンサブシーケンスを特定するステップとをさらに含む、ことを特徴とする請求項１に記載の方法。
【請求項６】
前記可能な分割位置のそれぞれに対して前記分割スコアを決定するステップは、
各可能な分割位置について、前記可能な分割位置に対する前記分割スコアを決定するために、前記可能なロケーションサブシーケンスとして特定された前記トークンサブシーケンスの前記ロケーション統計スコア、または前記可能なクエリサブシーケンスとして特定された前記トークンサブシーケンスの前記クエリ統計スコアの少なくとも１つを使用するステップを含む、ことを特徴とする請求項５に記載の方法。
【請求項７】
トークンサブシーケンスの前記ロケーション統計スコアまたは前記クエリ統計スコアの少なくとも1つが、統計モデルを参照することにより決定され、トークンサブシーケンスの前記ロケーション統計スコアが、前記トークンサブシーケンスがロケーションである確率を示し、および前記トークンサブシーケンスのクエリ統計スコアが、前記トークンサブシーケンスがクエリである確率を示す、ことを特徴とする請求項５に記載の方法。
【請求項８】
前記統計モデルが、タイトルおよびアドレスを含む訓練データに基づいて生成される、ことを特徴とする請求項７に記載の方法。
【請求項９】
訓練データアドレスが、前記訓練データアドレスの中のトレーリングタイトルを除去するために前処理され、および訓練データタイトルが、前記訓練データタイトルの中の接頭されている行政区名を除去するために、訓練データとして使用される前に前処理される、ことを特徴とする請求項８に記載の方法。
【請求項１０】
前記統計モデルが、
タイトルおよびアドレスを含む前記訓練データのそれぞれを、複数のトークンを含み、各トークンがタームと、前記タームにアノテートされたタイプとを含むトークンシーケンスにパーシングするステップと、
前記訓練データのトークン化されたタイトルおよびアドレス中に現れる複数の項目の発生回数をカウントおよび格納するステップと、により生成され、
複数の項目は、単一のタームから成るユニグラム、2つの隣接するタームから成るバイグラム、タイプ「None」を伴う隣接するタームから成るシーケンス、トークン化されたタイトルまたはアドレス内に現れる全てのタームのシーケンス、ユニグラムに関連するタイプから成るタイプユニグラム、バイグラムに関連するタイプから成るタイプバイグラム、またはシーケンスに関連するタイプから成るタイプのシーケンス、のうちのいずれか１つを複数含む、ことを特徴とする請求項８に記載の方法。
【請求項１１】
前記可能な分割位置の各々に対する前記分割スコアは、前記可能なロケーションサブシーケンスとして特定された前記トークンサブシーケンスの前記ロケーション統計スコアと、前記可能なクエリサブシーケンスとして特定された前記トークンサブシーケンスの前記クエリ統計スコアとの合計によって決定される、ことを特徴とする請求項６に記載の方法。
【請求項１２】
前記可能な分割位置について前記可能なクエリサブシーケンスのための前記クエリ統計スコアは、前記可能なクエリサブシーケンス中のトークン数に基づくクエリ乗数を含む、ことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記可能な分割位置について前記可能なクエリサブシーケンスのための前記クエリ統計スコアは、ロケーション乗数を含み、前記ロケーション乗数は、前記可能なロケーションサブシーケンスが、階層順にアドレスタイプのタームを有する場合、前記ロケーションに関連するベースロケーション乗数および付加的な乗数を含む、ことを特徴とする請求項１１に記載の方法。
【請求項１４】
トークンサブシーケンスのためのロケーション統計スコアまたはクエリ統計スコアを決定する前記ステップが、
前記トークンサブシーケンス中に現れる項目のスコアに基づいて、前記トークンサブシーケンスのためのタームスコアを決定するステップであって、前記項目のスコアは、訓練データの集成のタイトルおよびアドレス中の項目のカウントに基づく、ステップと、
前記トークンサブシーケンス中に現れる項目タイプのスコアに基づいて、前記トークンサブシーケンスのためのタームスコアを決定するステップであって、前記項目タイプのスコアは、訓練データの集成のタイトルおよびアドレス中の項目タイプのカウントに基づく、ステップと、
前記タームスコアおよび前記トークンシーケンスの前記タイプのスコアを加えるステップとを含む、ことを特徴とする請求項７に記載の方法。
【請求項１５】
ロケーション統計スコアを決定するための前記項目のスコアは、log(l_count)*l_count/(l_count+q_count)によって決定され、l_countおよびq_countは、訓練データの前記集成中のアドレスおよびタイトル内の前記項目の発生回数を表す、ことを特徴とする請求項１４に記載の方法。
【請求項１６】
クエリ統計スコアを決定するための前記項目のスコアは、log(q_count)*q_count/(l_count+q_count)によって決定され、l_countおよびq_countは、訓練データの前記集成中のアドレスおよびタイトル内の前記項目の発生回数を表す、ことを特徴とする請求項１４に記載の方法。
【請求項１７】
前記入力エントリの前記トークンシーケンスに前記パーシングするステップは、
前記トークンシーケンスの中で、誤ってアノテートされたタイプを有するトークンを修復するステップをさらに含む、ことを特徴とする請求項１に記載の方法。
【請求項１８】
前記トークンシーケンスの中で、誤ってアノテートされたタイプを有するトークンを修復する前記ステップは、
前記トークンが、前記タイプ「Number」のトークンに続かない場合、前記タイプ「数量サフィックス」のトークンを、前記タイプ「None」のトークンへと変更するステップを含む、ことを特徴とする請求項１７に記載の方法。
【請求項１９】
１または複数のコンピュータと、命令を格納する１または複数の記録装置とを具備するシステムであって、前記命令は、前記１または複数のコンピュータによって実行されるときに、
マップサーチのためにユーザから受信した入力エントリを１または複数のトークンのトークンシーケンスにパーシングするステップであって、各トークンは、前記入力エントリのセグメントを表すタームと、前記タームにアノテートされたタイプとを有し、前記タームにアノテートされた前記タイプは、前記タームがアドレス関連情報および前記アドレス関連情報のタイプを含むかどうかを示す、ステップと、
前記トークンシーケンスの可能な分割位置を決定するステップであって、可能な分割位置は、前記トークンシーケンスを１または２のサブシーケンスに分割する、ステップと、
前記可能な分割位置の各々に対する可能な分割方法を決定するステップであって、各可能な分割可能方法は、（１）ロケーション情報を示す可能なロケーション部と、（２）前記ロケーション部に関連する検索対象を示す可能なクエリ部との少なくとも１に、前記トークンシーケンスを分割する、ステップと、
前記可能な分割方法の各々の発生確率に対する分割スコアを決定するステップと、
結果として得られた分割方法として、最も高い分割スコアを有する前記可能な分割方法を選択するステップと、
前記結果として得られた分割方法の前記ロケーション部に基づいて地理的領域またはロケーションを取得するとともに、前記結果として得られた分割方法の前記クエリ部に関連し、かつ、前記取得された地理的領域またはロケーションの所に、中に、または近くに位置する１または複数のエンティティに関する情報を検索するためにマップサーチを実行するステップと、を含む動作を前記１または複数のコンピュータに実行させる、ことを特徴とするシステム。
【請求項２０】
命令を格納する機械読み取り可能な記録媒体であって、前記命令は、機械により実行されるとき、
マップサーチのためにユーザから受信した入力エントリを１または複数のトークンのトークンシーケンスにパーシングするステップであって、各トークンは、前記入力エントリのセグメントを表すタームと、前記タームにアノテートされたタイプとを有し、前記タームにアノテートされた前記タイプは、前記タームがアドレス関連情報および前記アドレス関連情報のタイプを含むかどうかを示す、ステップと、
前記トークンシーケンスの可能な分割位置を決定するステップであって、可能な分割位置は、前記トークンシーケンスを１または２のサブシーケンスに分割する、ステップと、
前記可能な分割位置の各々に対する可能な分割方法を決定するステップであって、各可能な分割可能方法は、（１）ロケーション情報を示す可能なロケーション部と、（２）前記ロケーション部に関連する検索対象を示す可能なクエリ部との少なくとも１に、前記トークンシーケンスを分割する、ステップと、
前記可能な分割方法の各々の発生確率に対する分割スコアを決定するステップと、
結果として得られた分割方法として、最も高い分割スコアを有する前記可能な分割方法を選択するステップと、
前記結果として得られた分割方法の前記ロケーション部に基づいて地理的領域またはロケーションを取得するとともに、前記結果として得られた分割方法の前記クエリ部に関連し、かつ、前記取得された地理的領域またはロケーションの所に、中に、または近くに位置する１または複数のエンティティに関する情報を検索するためにマップサーチを実行するステップと、を含む動作を前記機械に実行させる、ことを特徴とする機械読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この特許文書は、マップサーチのためのシステム、装置および方法を含む、マップサーチに関する。
【背景技術】
【０００２】
マップサーチは、例えばインターネットなどの1つまたは複数の通信ネットワークの中の、1つまたは複数のコンピュータサーバによって提供される、デジタル地図(digital geographic map)およびデータベースにおける、コンピュータベースの検索である。コンピュータユーザは、文書、ファイルまたはデータをデジタル地図および関連したデータベースから検索(search and retrieve)するコンピュータプログラムである、マップサーチエンジンを使用することができる。
【発明の概要】
【課題を解決するための手段】
【０００３】
ユーザクエリのパーシングに基づくマップサーチのための、コンピュータベースのシステム、装置および方法のための、実装形態が提供される。
【０００４】
一態様においては、コンピュータ実装されるマップサーチ方法が提供されて、マップサーチのためのユーザからの入力エントリを、入力検索エントリの中の位置情報を表すロケーション部と入力エントリの中のロケーション部に関連する検索対象を表すクエリ部へとパーシングするステップと、マップサーチを実施して、ロケーション部に基づいて地理的領域またはロケーションを取得し、また、クエリ部に関連し、かつ、取得された地理的領域またはロケーションの所に、中に、または近くに位置する1つまたは複数のエンティティに関する情報を検索するステップとを含む。
【０００５】
別の態様においては、コンピュータ実装されるマップサーチ方法が提供されて、マップサーチのためにユーザから受信された入力エントリを、1つまたは複数のトークンを含むトークンシーケンスへと分離するステップであって、各トークンが入力エントリのセグメントを表すタームと、タームにアノテートされ、タームの種類を表すタイプとを含むステップと、トークンシーケンスの可能な分割位置を決定するステップであって、可能な分割位置が、トークンシーケンスを1つまたは2つのサブシーケンスへと分割するステップとを含む。この方法はさらに、可能な分割位置のそれぞれに対する可能な分割方法を決定するステップであって、各可能な分割方法が、トークンシーケンスを(1)位置情報を表す可能なロケーション部および(2)ロケーション部に関連する検索対象を表す可能なクエリ部の少なくとも1つへと分割するステップと、可能な分割方法のそれぞれの正しさの確率に対する分割スコアを決定するステップと、最も高い分割スコアを有する可能な分割方法を、結果として得られた分割方法として選択するステップとを含む。
【０００６】
別の態様においては、コンピュータ実装されるマップサーチを提供するシステムが提供され、マップサーチのためにユーザから受信された入力エントリをロケーション部およびクエリ部の少なくとも1つへとパーシングするパーシングモジュールと、パーシングモジュールから出力を受信し、パーシングされたロケーション部およびクエリ部を受信した後、パーシングされたロケーション部およびクエリ部に関連する情報を検索して、マップサーチ結果をユーザに返す検索モジュールとを含む。一実装形態においては、このシステムは、通信をパーシングモジュールおよび検索モジュール、およびコンピュータに提供するコンピュータネットワークと、コンピュータネットワークと通信しており、ユーザからのマップサーチのための入力エントリを受信し、検索モジュールから結果を受信するクライアントコンピュータとを含むことができる。コンピュータネットワークは、クライアントコンピュータからの入力エントリをパーシングモジュールへ、結果を検索モジュールからクライアントコンピュータへと向かわせる。
【０００７】
別の態様においては、コンピュータ実装されるマップサーチを提供するシステムが提供されて、マップサーチのためにユーザから受信された入力エントリを、少なくとも1つのトークンを含むトークンシーケンスへとトークン化するトークンモジュールであって、各トークンが、入力エントリのセグメントを表すタームと、タームにアノテートされたタイプとを含む、モジュールと、トークンシーケンスの可能な分割位置を決定する手段であって、可能な分割位置がトークンシーケンスを1つまたは2つのサブシーケンスへと分割する、手段と、可能な分割位置のそれぞれに対して可能な分割方法を決定する手段であって、各可能な分割方法が、トークンシーケンスを可能なクエリ部および可能なロケーション部の少なくとも1つへと分割する、手段と、可能な分割方法のそれぞれに対して分割スコアを決定する手段と、最も高い分割スコアを有する可能な分割方法を、結果として得られた分割方法として選択する手段と、トークンモジュールからの出力を受信してマップサーチを実施し、マップサーチ結果をユーザに対して生成する検索モジュールとを含む。
【０００８】
別の態様においては、コンピュータ実装されるマップサーチを提供するシステムが提供され、ユーザにより入力された入力エントリを受信するインターフェースと、処理装置であって、入力エントリをパーシングして入力エントリをロケーション部およびクエリ部の少なくとも1つへと分割し、入力エントリに関連する情報をパーシング結果に基づいて検索する、処理装置とを含む。入力エントリが、ロケーション部とクエリ部とに分割された場合は、処理装置が、地理的領域をロケーション部に基づいて決定し、クエリ部に関連し、かつ、地理的領域内に位置するエンティティに関する情報を検索する。
【０００９】
別の態様においては、コンピュータ実装されるマップサーチを提供するシステムが提供され、ユーザにより入力された入力エントリを受信するインターフェースと、入力エントリを、少なくとも1つのトークンを含むトークンシーケンスへとトークン化し、トークンシーケンスの可能な分割方法を決定する処理装置とを含む。各トークンが、入力エントリのセグメントを表すタームと、タームにアノテートされたタイプとを含み、可能な分割位置がトークンシーケンスを1つまたは2つのサブシーケンスへと分割する。この処理装置は、可能な分割位置のそれぞれに対する可能な分割方法を決定し、各可能な分割方法が、トークンシーケンスを可能なクエリ部および/または可能なロケーション部へと分割し、可能な分割方法のそれぞれに対する分割スコアを決定し、最も高い分割スコアを有する可能な分割方法を、結果として得られた分割方法として選択する。
【００１０】
別の態様においては、命令を格納する機械読み取り可能な記録媒体が提供される。命令は、機械により実行されると、機械に、マップサーチのためのユーザからの入力エントリを、入力エントリに基づくマップサーチの実施に先立って、入力検索エントリの中の位置情報を表すロケーション部および入力エントリの中のロケーション部に関連する検索対象を表すクエリ部へとパーシングするステップと、マップサーチを実施させて、ロケーション部に基づいて地理的領域またはロケーションを取得し、クエリ部に関連し、かつ、取得された地理的領域またはロケーションの所に、中に、または近くに位置する1つまたは複数のエンティティに関する情報を検索するステップとを実行させる。
【００１１】
別の態様においては、複数の命令を記録する機械読み取り可能な記録媒体が提供される。命令は、機械により実行されると機械に、ユーザから受信された入力エントリを、少なくとも1つのトークンを含むトークンシーケンスへとトークン化し、各トークンがタームを含み、タームが入力エントリのセグメントおよびタームにアノテートされたタイプを表す動作と、トークンシーケンスの可能な分割位置を決定し、可能な分割位置が、トークンシーケンスを1つまたは2つのサブシーケンスに分割する動作と、可能な分割位置のそれぞれに対する可能な分割方法を決定し、各可能な分割方法が、トークンシーケンスを可能なクエリ部および/または可能なロケーション部へと分割する動作と、可能な分割方法のそれぞれに対する分割スコアを決定する動作と、最も高い分割スコアを有する可能な分割方法を、結果として得られた分割方法として選択する動作とを実行させる。
【００１２】
さらなる別の態様においては、コンピュータ実装されるマップサーチ方法が提供されて、マップサーチのためのユーザからの入力エントリを、入力エントリに基づくマップサーチの実施に先立って、入力検索エントリの中の位置情報を表すロケーション部および入力エントリの中のロケーション部に関連する検索対象を表すクエリ部へとパーシングさせるステップを含む。入力エントリのパーシングが、入力エントリにより示されるロケーションに対応するジオコードをあらかじめ検索することなしに実行される。この方法は、マップサーチを実施させて、ロケーション部に基づいて地理的領域またはロケーションを取得し、クエリ部に関連し、かつ、取得された地理的領域またはロケーションの所に、中に、または近くに位置する1つまたは複数のエンティティに関する情報を検索させるステップとを含む。
【００１３】
本明細書の中に記載されたコンピュータ実装されるマップサーチのための上記および他の態様は、効率的なマップサーチ、高精度なマップサーチ結果およびユーザへの迅速なマップサーチ結果の配信を含む、1つまたは複数の利益を実現するために実装形態されてよい。
【００１４】
コンピュータ実装されるマップサーチのためのシステム、装置および方法の上記のおよび他の態様の例および実装形態は、図面、記述および請求項の中で、詳細に記述される。
【図面の簡単な説明】
【００１５】
【図１】マップサーチのシステムおよび方法を含む、ネットワークシステム100の模範的な図である。
【図２】入力エントリをロケーション部とクエリ部とに分割するパーシングシステム200の、概念図である。
【図３】図2に示される辞書240の模範的な構造を説明する略図である。
【図４】統計モデルを訓練する例を説明するフローチャートである。
【図５】図2に示すモデル250の模範的な構造を説明する略図である。
【図６Ａ】入力エントリをパーシングする模範的な処理を説明するフローチャートである。
【図６Ｂ】入力エントリをパーシングする別の模範的な処理を説明するフローチャートである。
【図７Ａ】トークンシーケンスに対するロケーション統計スコアを計算する模範的な処理を説明する図である。
【図７Ｂ】トークンシーケンスのタームロケーションスコアを決定する模範的な処理を説明する図である。
【図７Ｃ】トークンシーケンスのタイプロケーションスコア決定する模範的な処理を説明する図である。
【図８Ａ】トークンシーケンスに対するクエリ統計スコアを計算する模範的な処理を説明する図である。
【図８Ｂ】トークンシーケンスのタームクエリスコアを決定する模範的な処理を説明する図である。
【図８Ｃ】トークンシーケンスのタイプクエリスコアを決定する模範的な処理を説明する図である。
【図９】マップサーチを実行する模範的な処理を説明するフローチャートである。
【図１０】本明細書において記述される技術を実装するための模範的な装置1000のブロック図である。
【発明を実施するための形態】
【００１６】
種々の図面における同様の参照符号は、同様の要素を意味する。
【００１７】
本明細書で記述されるマップサーチにおいては、マップサーチエンジンが、ユーザにより入力されたクエリに対する入力エントリを処理し、ユーザの関心を反映する1つまたは複数の検索結果を、入力エントリ内の情報に基づいて提供する。例えば、ユーザは、特定の地理的ロケーションに、中に、または近くに位置する特定のエンティティ(例えば、企業)または特定の種類のエンティティについての情報を検索してもよい。本明細書の中に記載されたマップサーチ方法およびシステムは、ユーザに、単一のボックスの中に入力エントリを入力させ、入力エントリの中に含まれる地理的ロケーションを表す入力エントリのロケーション部と、エンティティまたは特定の種類のエンティティを検索対象として表すことができる入力エントリのクエリ部とを、知的に認識するように実装されてもよい。例えば、単一のボックスに入力されたユーザ入力エントリ
【００１８】
【数１】
0005462361.tif 000002
【００１９】
(Yantai hotel)は、地理的ロケーションを規定するロケーション部
【００２０】
【数２】
0005462361.tif 000003
【００２１】
(Yantai)と、地理的ロケーションの中または近傍に位置する検索対象を表すクエリ部「酒店」(hotel)とにパーシングするように処理されうる。従って、マップサーチエンジンは、ユーザがYantai市に、中に、または近くにホテルを見つけるつもりだということと、マップサーチを実行するということを認識する。
【００２２】
入力エントリのロケーション部とクエリ部への分割すなわちパーシングにおいて、  入力エントリは、まず、1つまたは複数のセグメントにパーシングされ、これらセグメントはグループ分けされてロケーション部とクエリ部を構成する。パーシング中に、アドレス関連情報を表す文字(character)、文字(letter)、語(word)または語句のシーケンスが、そのようなものとして認識され、結果的に本明細書で「ターム」と称する単一の意味のあるセグメントとしてパーシングされる。このアドレス関連情報の認識は、例えば、アドレス関連情報を包含する1つまたは複数の辞書またはデータベースを使って達成されうる。
【００２３】
入力エントリのパーシング中に、パラメータ「type」がタームに割り当てられ、すなわちアノテーションされて、タームがアドレス関連情報を包含するかどうか、および、包含する場合は、タームが表すアドレス関連情報のタイプを示す。このタイプアノテーションは、マップサーチの精度を向上させるために用いられてよい。タイプアノテーションは、例えば、パーシング動作の中で使用されるアドレス関連情報を包含する、1つまたは複数の辞書またはデータベースを参照することにより実行されてよい。
【００２４】
タームにアノテーションされるタイプは、あらかじめ定められてもよい。例えば、タイプは、例えば「省」(province)、「市」(city)、「区」(district)、
【００２５】
【数３】
0005462361.tif 000004
【００２６】
(county)、
【００２７】
【数４】
0005462361.tif 000005
【００２８】
、「村」(village)などの行政区のレベルを、このような行政区を表すアノテーションタームのために含むことができる。タイプは同様に、「Road」というタイプを、タームが道路(road)または街路(street)を表すことを示すために含んでもよい。タイプは同様に、アドレスサフィックスまたはプリフィックス例えば「アドレスネームサフィックス」、「方向サフィックス」(例えば、南、北など)、およびタームが特定のアドレスサフィックスまたはプリフィックスに対応することを示すための「数値化サフィックス(Quantifier Suffix)」などを含むことができる。特に、「None」というタイプは、アドレス関連情報を表さないタームをアノテーションするために定義される。このタイプ「None」がタームに割り当てられたかどうかの判定は、マップサーチエンジンにより使用されるアドレス関連情報を包含する1つまたは複数の辞書またはデータベースの中のエントリに依存し、タイプ「None」は、実際の地理的ロケーションを表すタームに割り当てられてもよいが、それでもなお、パーシング動作の中で使用されるアドレス関連情報を包含する1つまたは複数の辞書またはデータベースの中ではマッチはしない。タームをアノテーションするためのタイプは、言語の特性に基づいて、さまざまな言語に対して明確に定義することができる。
【００２９】
一部の実装形態においては、パーシングは、マップサーチを実行する前に実行されてよい。このように、関連付けられたタイプが、アドレス関連情報を示し、かつ、「None」でない場合は、検索エンジンは、例えば、パーシング動作の結果のロケーション部を、ジオコードデータベースを検索して、ジオコード(geocode)として知られ経度および緯度によりまたは他の方法により示される地理コード(geographic code)を取得することによりロケーションをまず決定するために、用いることができる。タームに対するタイプが「None」の場合は、例えばタームのジオコードを検索することによるロケーションの決定は実行されない。ロケーションが決定された後、例えば、ロケーション部に関連するジオコードが見つかった後に、例えば、ジオコードにより定義されたロケーションまたはその近くでのクエリ部の検索が実行され、検索結果がユーザに配信される。まず入力エントリをパーシングしてロケーション部とクエリ部を抽出および特定し、その後例えばロケーション部に対するジオコードを検索することによりロケーションを決定するこのアプローチの実装形態は、最初の入力エントリまたはそのセグメントに基づいて前処理することなしに、例えば、最初の入力エントリまたはそのセグメントを、前処理をすることなしに一致するジオコードを検索するためにジオコードデータベースへ送信することによってマップサーチを実行することに依存することを避けるため、用いられてよく、マップサーチが、関連するマップサーチ結果を見つける上で高精度を伴って効率的に、また短い検索時間で実行されかつ配信されることを可能にすることができる。
【００３０】
本明細書において、パーシングおよびタイプアノテーションの動作は、集合的に「トークン化」と称する。入力エントリをセグメントへとパーシングし、タイプを入力エントリのセグメントにアノテートする(annotating)パーシング動作は、入力エントリをトークンのシーケンス、またはトークンシーケンスへとトークン化すると記述されてもよく、ここで、各トークンは、入力エントリのセグメントを表すタームと、タームにアノテートされ、どんな種類のアドレス関連情報をタームが表すかを示す、タイプとにより定義される。入力エントリのロケーション部とクエリ部は、トークンシーケンスをロケーション部とクエリ部へと分割することにより決定することができる。
【００３１】
入力エントリのロケーション部とクエリ部へのパーシングする一部の実装形態においては、統計モデルを、統計的なスコア付けを提供して入力エントリの種々の可能性のあるセグメントのさまざまなグループ分けを評価するために使用することができ、最高の統計的スコアを有するセグメントをパーシング動作の結果として選択することができる。本明細書における統計モデルは、訓練モデルに基づいて、および、例えばデータプロバイダ、政府機関、イエローページその他などの電話帳などの異なるデータソースから取得された訓練データを使って訓練されてもよい。訓練データは、アドレスと、エンティティの名称であるタイトル(例えば、企業名など)とを含む。訓練モデルにおいては、タイトルとアドレスのそれぞれは、トークンシーケンスへとトークン化され、タイトルの発生頻度とアドレスの発生頻度とは、トークンシーケンスに包含される、ターム、タイプ、ならびに特定のタームシーケンスおよびタイプシーケンスに関連して記録される。トークンシーケンスをロケーション部とクエリ部に分割する場合、スコアが、それぞれの可能な分割ごとに、統計モデルの中で記録された頻度に基づいて計算される。統計モデルによってもたらされるスコアに基づいて、特定のフィルタリングルールが、不適切な分割を除去して、真の分割を選択するために適用されてよい。
【００３２】
図1は、本明細書の中に記載されたマップサーチのシステムおよび方法の実装に適した、ネットワークシステム100の一例である。ネットワークシステム100は、通信をクライアント110とサーバ120に提供するネットワーク130を介して、1つまたは複数のサーバ120に接続された、またはこれらと通信している1つまたは複数のクライアント110を含む。図1の例は、簡単にするために、2つのクライアント110と2つのサーバ120を例示している。種々の実装形態においては、ネットワークシステム100は、より多くのまたはより少ないクライアント110およびサーバ120を含んでもよい。一部の実装形態においては、クライアント110は、サーバ120の一部の機能を実行してもよく、またサーバ120は、クライアント110の一部の機能を実行してもよい。マップサーチエンジンは、ネットワークシステム100の中に、例えば、1つまたは複数のサーバ120の中に、または1つまたは複数のサーバ120と1つまたは複数のクライアント110との両方の中になど、種々の構成で実装されてもよい。
【００３３】
クライアント110は、例えば携帯電話、パーソナルコンピュータ、携帯情報端末(PDA)、ラップトップなどの装置、またはこれらの装置の1つの上で作動しているスレッドまたはプロセス、および/またはこれらの装置の1つにより実行可能なオブジェクトを含む、さまざまな形態で実装されうる。各クライアント110は、入力エントリをユーザから受信し、入力エントリに対する検索結果をユーザに提供するマップサーチインターフェースと、入力エントリを1つまたは複数のサーバ120へと送信し、検索結果をネットワーク130を介して1つまたは複数のサーバ120から受信する通信インターフェースとを含む。
【００３４】
図1の例においては、各サーバ120は、ネットワーク130を介して受信された入力エントリをパーシングするためのマップサーチエンジンのパーシングシステム200と、パーシングシステム200のパーシング結果に基づいてマップサーチを実行して検索結果を返すマップサーチエンジンのマップサーチシステム140とを含む、サーバエンティティを含む。検索結果は、ネットワーク130を介してクライアント110に送信される。一部の実装形態においては、パーシングシステム200とマップサーチシステム140は、別々のサーバの中に駐在する。他の実装形態においては、パーシングシステム200は、マップサーチシステム140の一部として統合される。クライアント110およびサーバ120のそれぞれは、例えば、有線および無線通信リンクおよび接続などの1つまたは複数の通信リンクを介して、ネットワーク130に接続されてよい。
【００３５】
ネットワーク130は、例えば、ローカルエリアネットワーク(LAN)、広域ネットワーク(WAN)、都市規模ネットワーク(MAN)、電話ネットワーク、イントラネット、インターネット、またはこれらの2つ以上の組み合わせ、および他のネットワークなどの、種々の通信ネットワーク構成の中に実装されてよい。
【００３６】
図2は、ユーザからのクエリの入力エントリを、この入力エントリにより規定されるロケーションを表すロケーション部「where」と、このロケーションに関連する対象の検索要求を表すクエリ部「what」とに分割するすなわちパーシングする、パーシングシステム200の例を示す。例えば、入力エントリは、
【００３７】
【数５】
0005462361.tif 000006
【００３８】
(「Shanghai Restaurant」)でもよく、ここで
【００３９】
【数６】
0005462361.tif 000007
【００４０】
(「Restaurant」)はユーザ検索の対象がレストランであることを示すクエリ部であり、
【００４１】
【数７】
0005462361.tif 000008
【００４２】
(「Shanghai」)は、検索対象のロケーションが上海市の中または近傍にあることを示すロケーション部である。パーシングシステム200によるこのパーシングに基づき、マップサーチシステム140は、「Shanghai」の中または近傍の「Restaurant」を検索して、ユーザに配信するための検索結果を返す。
【００４３】
パーシングシステム200は、入力エントリをより小さな要素へとパーシングし、これらのより小さな要素すなわちセグメントをロケーション部とクエリ部とを構成するように処理するように設計される。パーシングシステム200によりパーシングされたこれらのより小さな要素すなわちセグメントは、小さすぎて、セグメントが互いに統計的にほとんど関連性がなくなり、かつ、意味のあるロケーション部およびクエリ部をこのような小さな要素から構成するために、多大な処理、従って時間遅れが必要となるようではならない。例えば、上記の入力エントリ
【００４４】
【数８】
0005462361.tif 000009
【００４５】
(「Shanghai Restaurant」)の例は、(1)個別の漢字「上」(up)、
【００４６】
【数９】
0005462361.tif 000010
【００４７】
(sea)、「餐」(eatingまたはfood)、および
【００４８】
【数１０】
0005462361.tif 000011
【００４９】
(building)、(2)「上」、
【００５０】
【数１１】
0005462361.tif 000012
【００５１】
、および
【００５２】
【数１２】
0005462361.tif 000013
【００５３】
、(3)
【００５４】
【数１３】
0005462361.tif 000014
【００５５】
(Shanghai)および
【００５６】
【数１４】
0005462361.tif 000015
【００５７】
(Restaurant)のように、種々のセグメントに分割することができる。パーシングされたセグメントは、(1)および(2)の例においては、ロケーション部とクエリ部を構成するには有用性が低く、所望のロケーション部とクエリ部とを構成するためには、これら小さな要素の追加の区分けとグループ分けが必要となる。例(3)でパーシングされた要素は、対照的に、適切なロケーション部(Shanghaiに対する
【００５８】
【数１５】
0005462361.tif 000016
【００５９】
)とクエリ部(restaurantに対する
【００６０】
【数１６】
0005462361.tif 000017
【００６１】
)である。特定の言語は、その言語の特定の性質のためにユーザからの入力エントリをパーシングする上で、課題を提示する。例えば、英語のユーザクエリは、例えば、「Shanghai」と「Restaurant」がスペースで分離されている「Shanghai Restaurant」などのように、2つの隣接する単語間に間隔のある文字でできた英単語で構成される。英語の2つの隣接する単語間のこのようなスペーシングは、入力エントリを分割するための自然の境界を提供する。しかしながら、中国語、日本語、または韓国語のユーザクエリのための入力エントリは、例えば、
【００６２】
【数１７】
0005462361.tif 000018
【００６３】
(Shanghai Restaurant)のように、2つの隣接する文字の間にスペーシングのない連続的な文字のシーケンスでありうる。本明細書の中に記載されるパーシングシステム200は、アドレスおよび他のロケーションを表す上で使用される、ロケーション、名称、サフィックス、プリフィックスを含むアドレス関連情報の1つまたは複数の辞書と、入力エントリから位置情報を抽出し適切なロケーション部とクエリ部とを構成する名称データベースとに基づいてパーシング知能を有するように設計されてよい。
【００６４】
一例として、パーシングシステム200は、1つまたは複数のアドレス関連情報の辞書またはデータベースに基づくトークナイザを含むように実装されて、ユーザクエリの入力エントリを、入力エントリ内のロケーション名がトークナイザにより単一のセグメントとして維持されるようにするようにパーシングしてよい。このトークナイザは、入力エントリのパーシングを実行するための、行政団体(administration entity)名、地域名、道路名、および種々のサフィックス、プリフィックスを包含する辞書を使用して、ロケーション名である入力エントリ内の1つのセグメントの好ましくない分割を最小化することができる。例えば、中国語入力エントリの中に包含される中国語街路名「城府路」(Chengfu Road)は、小さい要素に分割される代わりに、パーシングシステム200により1つのセグメントとして維持されてよい。このようなアドレス情報で認識されるパーシングの検索精度および検索レスポンスタイムは、アドレス関連情報を認識せず、入力エントリに包含されるロケーション名を、例えば、中国語街路名「城府路」を個別の漢字の「城」(cheng)、「府」(fu)、および「路」(road)へなどのように、より小さい要素に分割するセグメンテータシステムを使うよりも優れている傾向がある。一部の実装形態においては、トークナイザは、タイプを入力エントリのセグメントにアノテートして、このセグメントがアドレス関連情報を表すかどうか、また、もしそうなら、セグメントが表すアドレス関連情報の種類を示すことができる。
【００６５】
図2のパーシングシステム200は、トークンベースのパーシングシステムであり、説明される例においては、トークン化モジュール210、モデル訓練モジュール220、パーシングモジュール230、辞書240およびモデル250を含む。これらのモジュールは集合的に動作して、パーシングモジュール230が、マップサーチを実行するために、入力エントリをロケーション部とクエリ部へとパーシングすることを可能にする。トークン化モジュール210は、ロケーション名の辞書240からの位置情報に基づいて、入力エントリをトークンへとトークン化する。パーシングモジュール230は、外部からの入力エントリを受信し、この入力エントリをトークン化のためにトークン化モジュール210に送信し、トークン化モジュール210からトークンを受信して、受信されたトークンをトークン、トークンのシーケンスおよびモデル250からの他の項目の統計的得点に基づいて処理して、パーシング動作を実行する。モデル250は、1つまたは複数のデータソースから取得される訓練データを受信および処理するモデル訓練モジュール220により生成され、かつ訓練される。
【００６６】
トークン化モジュール210は、例えば、辞書240から取得されうるアドレス関連およびロケーション関連情報に基づいて、入力エントリをトークンへとトークン化する。実装形態においては、トークンは、入力エントリのセグメントを表すタームと、このタームにアノテートされたタイプとを含むように定義されて、タームがアドレス関連情報を表すかどうか、もしそうなら、どんな種類のアドレス関連情報をタームが表すのかを示すことができる。トークン化モジュール210は、アドレス関連情報を認識することができ、アドレス関連情報を意味のあるトークンへとトークン化する。例えば、入力エントリの中の中国語の語句「成府路」は、トークン化モジュール210により、道路名として認識されて、語句「城府路」からなる単一のトークンをタームとして、かつ、タイプ「Road」を、語句「城府路」が道路名を表すことを示すパラメータとしてトークン化されてもよい。トークン化モジュール210は、アドレス関連またはロケーション関連情報の辞書240を使用してトークン化を実行することができる。辞書240は、アドレス関連情報を格納する。
【００６７】
図3は、辞書240の模範的な構造を説明する略図である。辞書240は、辞書エントリ(DE: dictionary entry)300を有し、各DE300は、タームフィールド310とタイプフィールド320の2つのフィールドを有する。タームフィールド310は、アドレス関連情報を表すタームすなわち語句を格納する。タームは、例えば、「北京市」(Beijing City)、
【００６８】
【数１８】
0005462361.tif 000019
【００６９】
(Chaoyan District)、
【００７０】
【数１９】
0005462361.tif 000020
【００７１】
(Chaoyan)などの行政区名、または、
【００７２】
【数２０】
0005462361.tif 000021
【００７３】
(Changde Road)および「城府路」(Chengfu Road)などの道路名などのアドレス名でありうる。タームは同様に、アドレス関連サフィックスまたはアドレス関連プリフィックスを表すことができる。例えば、タームは、例えば「省」(province)、「市」(city)、「区」(District)、
【００７４】
【数２１】
0005462361.tif 000022
【００７５】
(county)、
【００７６】
【数２２】
0005462361.tif 000023
【００７７】
、「村」(village)、「路」(road)、「道」(road)などのアドレスネームサフィックス、例えば
【００７８】
【数２３】
0005462361.tif 000024
【００７９】
(East)、「西」(West)、「南」(South)、「北」(North)、
【００８０】
【数２４】
0005462361.tif 000025
【００８１】
(Northeast)、
【００８２】
【数２５】
0005462361.tif 000026
【００８３】
(Southeast)、「西北」(Northwest)、「西南」(Southwest)などの方向プリフィックスもしくはサフィックス、または、例えば「号」(Number)などの数量サフィックスでありうる。タームは同様に、アドレス、例えば、番号を記述するために用いられうる他の単語や表現でもよい。DE300のタイプフィールド320は、タームが表すアドレス関連情報の種類を示すタイプを包含する。種々のタイプが、定義されてよい。例えば、タイプは、例えば「省」(province)、「市」(city)、「区」(District)、
【００８４】
【数２６】
0005462361.tif 000027
【００８５】
(county)、
【００８６】
【数２７】
0005462361.tif 000028
【００８７】
、「村」(village)などの行政区のレベル、例えば「アドレスネームサフィックス」、「方向サフィックス」などのアドレスサフィックスまたはプリフィックス、および「数量サフィックス」を含む。タイプは同様に、対応するタームが道路名を表すために定義された「Road」タイプ、および対応するタームが番号、例えば街路番号を表すために定義された「Number」タイプを含んでよい。他のタイプも同様に、必要に応じて定義されてよい。随意的に、辞書240のDE300はさらに、例えば、アラビア語、中国語、英語、ドイツ語、日本語、韓国語などのタームの言語を示す言語フィールド330を有する。一部の実装形態においては、辞書240は例えば既存のアドレス情報データベースなどの既存のデータ上に構築されてよい。一部の実装形態においては、辞書の辞書エントリは、必要に応じて事前に定義してもよい。
【００８８】
図2に戻ると、トークン化モジュール210は、入力エントリを受信し、入力エントリをトークンへとトークン化し、トークン化された結果をトークンシーケンスとして出力する。一部の実装形態においては、トークン化モジュール210はまず、辞書240に基づいてトークン化を実行し、入力エントリの中のアドレス関連単語すなわちセグメントを認識するようにする。一例として、トークン化モジュール210は、辞書240に基づいてトークン化を実行する、フォワードマキシマムマッチング(FMM: Forward Maximum Matching)を使用する。このFMM手法は、いくつかの文字(例えば、漢字)をイニシャル最大ストリング(initial maximum string)として包含しているストリングを選択し、イニシャル最大ストリングが辞書240の中のタームにマッチするかどうかを判断する。イニシャル最大ストリングが辞書240内の任意のタームにマッチしない場合は、イニシャル最大ストリングから1文字減らすことによりマッチングの判定が継続され、マッチするタームが辞書240の中に見つかるまで、またはストリングが空になるまで、残りの文字を包含するストリングが、辞書240内のタームにマッチするかどうかを判断する。辞書240の中で見つかったマッチするタームと、マッチしたタームに関連するタイプは、トークンのタームとタイプになる。FMM手法に加えて、例えば、バックワードマキシマムマッチング(BMM: Backward Maximum Matching)手法、およびバイディレクショナルマッチング(BM: Bi-direction Matching)手法などの他の方法を、使用してもよい。FMM手法、BMM手法およびBM手法を実装するための一部の例は、既刊文献の中で見つけることができる。
【００８９】
辞書240に基づく上記の処理は、ロケーションを表す可能性のある、入力エントリの1つまたは複数の部分を特定する。一部の実装形態においては、トークン化モジュール210は、数を認識し、もし特定の数字が辞書240の中にタームとして格納されていない場合でさえも、これを「Number」タイプを伴うトークンへとトークン化することができる。一部の実装形態においては、アドレス関連情報として認識されない入力エントリの一部、例えば、辞書240の中にマッチするタームのない入力エントリの一部に対して、トークン化モジュール210は、これらを単語に分割し、これらの単語をトークンのタームとし、トークンの種類を「None」としてアノテートすることができる。タイプ「None」は、対応するタームが、辞書240において定義されたいかなるタイプにも属しないことを示し、この対応するタームは、アドレス関連情報を表さない。例えば、中国語入力エントリの「城大灯具城」(「Chengda Lamps and Lanterns Market」)をトークン化する場合は、トークン化モジュール210は、「城大」(「Chengda」)に対する辞書エントリをロケーション名として持っていない辞書240を参照することにより、中国語の語句「城大」(「Chengda」)がロケーション名ではないということを判断することができる。
【００９０】
トークン化モジュール210により生成されたトークンは、統計モデル250によってもたらされる統計的スコアに結び付けられ、パーシングモジュール230は、入力エントリのロケーション部とクエリ部へのパーシングにおいてこの統計的スコアを考慮する。パーシングシステム200のモデル訓練モジュール220は、統計モデル250を訓練および更新するために提供される。
【００９１】
図4は、統計モデル250を訓練するためのモデル訓練モジュール220により実行される処理400の、一例を説明するフローチャートである。
【００９２】
モデル訓練モジュール220は、ステップS410で、訓練データを1つまたは複数のソースから取得する。一部の実装形態においては、訓練データは、2-ボックスクエリログから取得することができる。2-ボックスログの品質が高性能検索に対して不十分なアプリケーションにおいては、訓練データは、他のソースから取得されてよい。例えば、訓練データは、例えば企業体または政府部門などのデータプロバイダにより提供されうる。訓練データは同様に、例えばイエローページや地図データベース等の他のソースからも取得することができる。訓練データは、アドレスとタイトルとを含む。タイトルは、エンティティの名称、例えば、「Google」のような企業名、
【００９３】
【数２８】
0005462361.tif 000029
【００９４】
(Kejian Building)のようなビルディング名、「北京市政府」(Beijing City Government)のような官庁名を表す。アドレスの例には、
【００９５】
【数２９】
0005462361.tif 000030
【００９６】
(No.29 of Zhun Guan Cun Boulevard, Haidian District, Beijing City)が含まれる。一部の実装形態においては、もともと取得された生データは、訓練データとして使用される前に、前処理される必要がある。生データの前処理とは、例えば、タイトルの中の行政区のプリフィックス名、アドレスの中のトレーリングタイトル(trailing title)などの、データの不必要な部分を除去することである。
【００９７】
例えば、タイトルの生データの1個が
【００９８】
【数３０】
0005462361.tif 000031
【００９９】
(Haidian Hospital in Haidian District of Beijing City)であるとすると、前処理はこれを、プリフィックスしている行政区名
【０１００】
【数３１】
0005462361.tif 000032
【０１０１】
((Haidian District of Beijing City)を除去することにより純粋なタイトル
【０１０２】
【数３２】
0005462361.tif 000033
【０１０３】
(Haidian Hospital)へとフィルタリングする。別の例としては、アドレスの生データの1個が
【０１０４】
【数３３】
0005462361.tif 000034
【０１０５】
(Haidian Hospital, No.29 of Zhun Guan Cun Boulevard, Haidian District, Beijing City)だとすると、前処理はこれを、サフィックスしている病院名
【０１０６】
【数３４】
0005462361.tif 000035
【０１０７】
(Haidian Hospital)を除去することにより純粋なアドレス
【０１０８】
【数３５】
0005462361.tif 000036
【０１０９】
(No. 29 of Zhun Guan Cun Boulevard, Haidian District, Beijing City)へとフィルタリングする。
【０１１０】
ステップS420において、モデル訓練モジュール220は、前処理されている訓練データの中のタイトルおよびアドレスの中の1つをトークン化モジュール、例えば、トークン化モジュール210へと送信して、およびこのトークン化モジュールからトークン化結果としてのタームおよびタイプを伴うトークンのトークンシーケンスを受信して、トークン化を実行する。随意的に、タイプ修復(type fixing)がステップS430で実行され、トークンシーケンスの中の誤ってアノテートされたタイプを修復する。タイプ修復は、ある規定のルールに従って実行される。例えば、ルールは、「数量サフィックス」というタイプを持つタームが「Number」タイプを伴うタームに続かない場合は、タイプ「数量サフィックス」は、タイプ「None」に変更されるということを規定することができる。例えば、アドレス
【０１１１】
【数３６】
0005462361.tif 000037
【０１１２】
(No. 29 of Zhun Guan Cun Boulevard)をトークン化した後、ターム"29"がタイプ「Number」を伴って取得され、ターム「号」(number)がタイプ「数量サフィックス」を伴って取得される。「数量サフィックス」のタイプを伴うターム「号」(number)は、「Number」のタイプを伴うターム「29」に続いているので、「号」(number)のタイプは変更されない。しかしながら、タイトル
【０１１３】
【数３７】
0005462361.tif 000038
【０１１４】
(China Time-honored Brand Donglaishun)をトークン化した後では、ターム「号」は、「数量サフィックス」のタイプを伴って取得されてもよいが、同じ漢字「号」はもはや数を表さず、むしろ会社のブランド設定を表す。従って、タイプは、タイプ「None」に変更されることになる。随意的に、トークンシーケンスの中の、タームが同じサフィックスまたはプリフィックスタイプを持つ隣接するトークンは、ステップS440で、単一のトークンに結合されてよい。
【０１１５】
ステップS450で、タイトルおよびアドレスにおける発生回数が、タイプおよびタームに関して、トークンシーケンスの中でそれぞれ数えられる。一部の実装形態においては、カウントは、トークンシーケンスの中の特定のタイプシーケンスおよびタームシーケンスに対して実行される。一実装形態においては、タイトルとアドレスにおける発生回数は、以下の項目、
-単一のタームである、タームユニグラム(term unigram)、
-2つの隣接するタームから成るタームシーケンスである、タームバイグラム(term bigram)、
-タイプ「None」を伴う隣接するタームのシーケンス、
-全てのタームのシーケンス、
-単一のタイプである、タイプユニグラム(type unigram)、
-2つの隣接するタイプから成るタイプシーケンスであるタイプバイグラム(type bigram)、および
-全てのタイプのシーケンス、に対してカウントされる。例えば、住所
【０１１６】
【数３８】
0005462361.tif 000039
【０１１７】
(Beijing, Chaoyang District, Datun Road)が、数個のトークン、［ターム:北京(Beijing)、タイプ:市(City)］、［ターム:
【０１１８】
【数３９】
0005462361.tif 000040
【０１１９】
(Chaoyang)、タイプ:区(District)］、および［ターム:
【０１２０】
【数４０】
0005462361.tif 000041
【０１２１】
(Datun Road)、タイプ:Road］を含むトークンシーケンスへとトークン化される場合は、以下の項目に対するアドレス中の発生のカウントは、
タームユニグラム:「北京」(Beijing)、
【０１２２】
【数４１】
0005462361.tif 000042
【０１２３】
(Chaoyang)、
【０１２４】
【数４２】
0005462361.tif 000043
【０１２５】
(Datun Road);
タームバイグラム:
【０１２６】
【数４３】
0005462361.tif 000044
【０１２７】
(Chaoyang of Beijing)、
【０１２８】
【数４４】
0005462361.tif 000045
【０１２９】
(Datun Road, Chaoyang);
全てのタームのシーケンス:
【０１３０】
【数４５】
0005462361.tif 000046
【０１３１】
(Datun Road, Chaoyang, Beijing);
タイプユニグラム:「市」(City)、「区」(District)、「路」(Road);
タイプバイグラム:「市、区」(City, District)、「区、路」(District, Road);
全てのタイプのシーケンス:「市、区、路」(City、District、Road);ということになる。
上述の項目において、タイプ「None」を伴う隣接するタームのシーケンスは、この例の中ではカウントされない。なぜなら、トークンシーケンス［ターム:北京(Beijing)、タイプ:市(City)］、［ターム:
【０１３２】
【数４６】
0005462361.tif 000047
【０１３３】
(Chaoyang)、タイプ:区(District)］、および［ターム:
【０１３４】
【数４７】
0005462361.tif 000048
【０１３５】
(Datun Road)、タイプ:路(Road)］の中には、タイプ「None」を伴うタームはないからである。
【０１３６】
各カウントされる項目ごとに、タイトルの中でのその発生の回数およびアドレスの中でのその発生の回数が、ステップS460で、それぞれモデル250の中に格納される。
【０１３７】
図5は、モデル250の模範的な構造を説明する。モデル250は、モデルエントリ(ME:model entry)500を含む。各カウントされる項目は、モデル250の中に、対応するモデルエントリを有する。1つの実装形態においては、モデルエントリは4つのフィールド:
-「項目」フィールド510であって、タームユニグラム、タイプユニグラム、ならびに、タイプ「None」を伴う隣接するタームのシーケンス、全てのタームのシーケンス、タイプバイグラム、および全てのタイプのシーケンスを含む、タームまたはタイプのシーケンス、の1つの内容を記録するフィールドと、
-「項目タイプ」フィールド520であって、項目が、タームユニグラム、タイプユニグラム、タイプバイグラム、タームバイグラム、タイプ「None」を伴う隣接するタームのシーケンス、全てのタームのシーケンス、および全てのタイプのシーケンス、という項目タイプの中の、どのタイプであるかを記録するフィールドと、
-「タイトルの中の発生回数」フィールド530であって、対応する項目がタイトルの中で何回発生するかを記録するフィールドと、
-「アドレスの中の発生回数」フィールド540であって、対応する項目がアドレスの中で何回発生するかを記録するフィールドとを有する。一部の実装形態においては、モデルエントリは同様に、5番目のフィールドであり、項目の言語を示す「言語」フィールド550を持つことができる。
【０１３８】
アドレス
【０１３９】
【数４８】
0005462361.tif 000049
【０１４０】
(Beijing Chaoyang Datun Road)に対する項目
【０１４１】
【数４９】
0005462361.tif 000050
【０１４２】
(Chaoyang Datun Road)がステップS450でカウントされる例を考える。既存のモデルエントリであって、その「項目」フィールド、「項目タイプ」フィールド、および、もしあれば「言語」フィールドが、全て項目
【０１４３】
【数５０】
0005462361.tif 000051
【０１４４】
にマッチするものがない場合は、
【０１４５】
【数５１】
0005462361.tif 000052
【０１４６】
(Chaoyang Datun Road)に対するモデルエントリが、
【０１４７】
【数５２】
0005462361.tif 000053
【０１４８】
と値を付けられた「項目」フィールド、「タームバイグラム」と値を付けられた「項目タイプ」フィールド、0と値を付けられた「タイトルの中の発生回数」フィールド、1と値を付けられた「アドレスの中の発生回数」フィールド、および「中国語」と値を付けられた「言語」フィールド、を伴って生成される。
【０１４９】
「項目」フィールド、「項目タイプ」フィールド、および「言語」フィールドが、全て項目
【０１５０】
【数５３】
0005462361.tif 000054
【０１５１】
(Chaoyang Datun Road)にマッチする既存のモデルエントリが既に存在する場合は、このモデルエントリの「アドレスの中の発生回数」フィールドの値は、1だけ増加され、このモデルエントリの他のフィールドの値は、依然として変えられない。具体例として、タイプが「全てのタイプのシーケンス」である、項目「市、区、路」(City、District、Road)が、アドレス
【０１５２】
【数５４】
0005462361.tif 000055
【０１５３】
(Beijing Chaoyang Datun Road)に対してカウントされる別の例を考える。「項目」フィールドが「市、区、路」(City, District, Road)であり、「項目タイプ」フィールドが「全てのタイプのシーケンス」であり、「言語」フィールドが「中国語」である既存のモデルエントリがある場合、すなわち、「項目」フィールド、「項目タイプ」フィールドおよび「言語」フィールドが全て項目「市、区、路」(City, District, Road)にマッチする既存のエントリがある場合は、モデルエントリの「タイトルの中の発生回数」の値および「言語」フィールドの値は、依然として変化せず、モデルエントリ「アドレスの中の発生回数」フィールドの値は、1だけ増加される。
【０１５４】
ステップS470で、訓練モデルは全てのタイトルおよびアドレスが処理されているかどうかを調べる。全てのタイトルおよびアドレスが処理された場合は、統計モデル250を訓練する処理400は終了し、統計モデル250は、ユーザクエリからの入力エントリのパーシングにおいてパーシングモジュール230により使用されるために生成されるかまたは更新される。そうでなければ、処理400は、ステップS420に戻り、次のタイトルまたはアドレスを処理する。
【０１５５】
モデル訓練モジュール220による統計モデル250の訓練は、さまざまな方法で実装されてよい。一部の実装形態においては、例えば、モデル訓練モジュール220は、統計モデル250をシステム200の動作の初めに訓練し、また統計モデル250を周期的にまたは特定の事象が発生したときに、例えば、訓練データが更新されたときに更新する。
【０１５６】
モデル訓練モジュール220により生成された統計モデル250は、パーシングモジュール230が、項目、トークンまたはトークンシーケンスのためのロケーション統計スコアおよびクエリ統計スコアを決定するために使用されうる。ここで、「項目」は、それに対してタイトルおよびアドレスにおける発生回数がカウントされる項目、すなわち、タームユニグラム、タームバイグラム、タイプ「None」を伴う隣接するタームのシーケンス、全てのタームのシーケンス、タイプユニグラム、タイプバイグラム、または全てのタイプのシーケンスを示す。項目、トークンまたはトークンシーケンスのロケーション統計スコアは、項目、トークンまたはトークンシーケンスがロケーションに関連している確率を示す。項目、トークンまたはトークンシーケンスのクエリ統計スコアは、項目、トークンまたはトークンシーケンスがクエリに、すなわち、エンティティ名またはエンティティカテゴリに関連する確率を示す。
【０１５７】
一部の実装形態においては、項目が、統計モデル250の中に対応するエントリを有する場合は、この項目のロケーション統計スコアおよびクエリ統計スコアは、方程式(1)および(2)を使ってそれぞれ計算される。
項目のロケーション統計スコア=log(l_count)*l_count/(l_count+q_count)
---方程式(1)
項目のクエリ統計スコア=log(q_count)*q_count/(l_count+q_count)
---方程式(2)
ここで、l_countおよびq_countは、アドレスおよびタイトルにおける項目の発生回数をそれぞれ表し、これらは、統計モデル250の中に格納される。例えば、タームユニグラム
【０１５８】
【数５５】
0005462361.tif 000056
【０１５９】
(Chaoyang)の項目のロケーションおよびクエリ統計スコアを計算する場合は、アドレスおよびタイトルにおけるタームユニグラム
【０１６０】
【数５６】
0005462361.tif 000057
【０１６１】
(Chaoyang)の発生回数が、それぞれN1およびN2ならば、この項目のロケーション統計スコアは、logN1*N1/(N1+N2)のように計算され、またこの項目のクエリ統計スコアは、logN2*N2/(N1+N2)のように計算される。項目が、統計モデル250の中に対応するエントリを有しない場合は、この項目のロケーション統計スコアおよびクエリ統計スコアは、「0」の値を与えられる。
【０１６２】
一部の実装形態においては、トークンのロケーション統計スコアは、このトークンのターム(タームユニグラム)のロケーション統計スコアおよびこのトークンのタイプ(タイプユニグラム)のロケーション統計スコアの合計として定義される。
【０１６３】
トークンシーケンスに対するロケーション統計スコアおよびクエリ統計スコアを、統計モデル250に基づいて計算する模範的な方法が、以下に記述される。
【０１６４】
図7Aは、トークンシーケンスに対するロケーション統計スコアを計算する模範的な処理700Aを例示する。ステップS710において、トークンシーケンスに対するタームロケーションスコアが決定される。タームロケーションスコアは、トークンシーケンスのタームに関して、項目のロケーション統計スコアに基づいて決定された統計的スコアである。一実装形態における、トークンシーケンスのタームロケーションスコアを決定する処理が、図7Bの中で例示され、また以下で説明される。ステップS720で、タイプロケーションスコアがトークンシーケンスに対して決定される。タイプロケーションスコアは、トークンシーケンスのタイプに関して、項目のロケーション統計スコアに基づいて決定された統計的スコアである。一実装形態におけるトークンシーケンスのタイプロケーションスコアを決定する処理が、図7Cの中で例示され、以下に説明される。ステップS730で、トークンシーケンスのロケーション統計スコアが、トークンシーケンスのタームロケーションスコアおよびタイプロケーションスコアを合計することにより決定される。
【０１６５】
図7Bは、トークンシーケンスのタームロケーションスコアを決定する模範的な処理700Bを示す。ステップS7102で、トークンシーケンスの中の第1のトークンをカレントトークン(current token)と定義する。ステップS7104で、統計モデル250を参照することにより、トークンシーケンスの以下の項目:カレントトークンのタームで始まる、カレントトークンの「タームユニグラム」、ならびに「タームバイグラム」および「タイプ「None」を伴う隣接するタームのシーケンス」(以上のような項目が存在する場合)、に対するロケーション統計スコアを決定する。ステップS7108では、ステップS7104において決定されたロケーション統計スコアの中で最も高いものが、カレントトークンのタームロケーションスコアとして選択される。ステップS7112では、トークンシーケンスの中にネクストトークン(next token)があるかどうかを決定し、この判定の結果がYes(ステップS7112でYes)の場合は、このネクストトークンが、カレントトークンのタームロケーションスコアを決定するときに考慮されたかどうかを、ステップS7114で判断する。このネクストトークンが考慮されていた場合は(ステップS7114でYes)、考慮されたトークンはスキップされ、処理700Bは、ステップS7112に進み、そうでなければ(ステップS7114でNo)、ネクストトークンがカレントトークンのタームロケーションスコアを決定するときに考慮されていない場合は、ネクストトークンは、カレントトークンと定義され(ステップS7116)、処理700BはステップS7104に戻る。ステップS7112で、トークンシーケンスの中にネクストトークンがないと判断された場合は(ステップS7112のNo)、処理700Bは、ステップS7118に進み、得られたトークンのタームロケーションスコアをスコアS1として合計する。次に、トークンシーケンスの項目「全てのタームのシーケンス」のロケーション統計スコア(スコアS2と呼ぶ)が、ステップS7120において、統計モデル250を参照することにより決定される。ステップS7126で、スコアS1および2を比較して、スコアS1がスコアS2に等しいかまたは大きい場合(ステップS7126でYes)は、トークンシーケンスのタームロケーションスコアは、スコアS1と決定され(ステップS7128)、そうでなければ、スコアS1がスコアS2より小さい場合は(ステップS7126でNo)、トークンシーケンスのタームロケーションスコアは、スコアS2と決定され(ステップS7130)、その後処理700Bは完了する。
【０１６６】
次に、トークンシーケンスのタイプロケーションスコアを決定する模範的な処理700Cが、図7Cを参照して説明される。ステップS7202で、トークンシーケンスの中の第1のトークンをカレントトークンとして定義する。ステップS7204で、トークンシーケンスの以下の項目:カレントトークンの「タイプユニグラム」、および、もし存在するなら、カレントトークンのタイプで始まる「タイプバイグラム」、に対するロケーション統計スコアを、統計モデル250を参照することにより決定する。ステップS7208で、ステップS7204の中で決定された、より高いロケーション統計スコアが、カレントトークンのタイプロケーションスコアとして選択される。カレントトークンが、トークンシーケンスの中の最後のトークンの場合は、カレントトークンのタイプを伴って始まる"タイプバイグラム"は、もちろん存在せず、このカレントトークンのタイプロケーションは、「タイプユニグラム」のロケーション統計スコアである。ステップS7212で、トークンシーケンスの中にネクストトークンがあるかどうかを判定し、判定結果がYes(ステップS7212でYesの場合は)、ネクストトークンが、カレントトークンのタイプロケーションスコア決定するときに考慮されたかどうかをステップS7214で判定する。ネクストトークンが考慮されていた場合は(ステップS7214でYes)、考慮されたトークンはスキップされ、処理700CはステップS7212に進む。そうでなければ、ネクストトークンがカレントトークンのタイプロケーションスコアを決定するときに考慮されていない場合は(ステップS7214でNo)、ネクストトークンは、カレントトークンと定義され(ステップS7216)、処理700CはステップS7204に戻る。ステップS7212で、トークンシーケンスの中にネクストトークンがないと判断された場合は(ステップS7212でNo)、処理は、ステップS7218に進み、得られたトークンのタイプロケーションスコアを合計し、この結果はスコアS3と記される。次に、トークンシーケンスの項目「全てのタイプのシーケンス」のロケーション統計スコア(このスコアはスコアS4と記される)を、統計モデル250を参照することにより、ステップS7220で決定する。ステップS7226で、スコアS3および4を比較し、スコアS3がスコアS4に等しいかまたは大きい場合は(ステップS7226でYes)、トークンシーケンスのタイプロケーションスコアがスコアS3と決定される(ステップS7228)。そうでなければ、スコアS3がスコアS4より少ない場合は(ステップS7226でNo)、トークンシーケンスのタイプロケーションスコアは、スコアS4と決定される(ステップS7230)。その後、処理700Cは、完了する。
【０１６７】
トークンシーケンスのクエリ統計スコアは、ロケーション統計スコアと同様に決定されてよい。図8Aは、トークンシーケンスに対するクエリ統計スコアを計算する、模範的な処理800Aを説明する。トークンシーケンスのクエリ統計スコアは、トークンシーケンスのタームクエリスコアおよびタイプクエリスコアを合計することにより決定することができる。ここで、タームクエリスコアは、項目のクエリ統計スコアに基づいてトークンシーケンスのタームに関して決定される統計的スコアであり、タイプクエリスコアは、項目のクエリ統計スコアに基づいてトークンシーケンスのタイプに関して決定される統計的スコアである。
【０１６８】
図8Bは、トークンシーケンスのタームクエリスコアを計算する模範的な処理800Bを例示し、図8Cは、トークンシーケンスのタイプクエリスコアを計算する模範的な処理を例示する。図8A〜8Cの詳細な動作は、図7A〜7Cに対する関連のある説明を参照することにより理解することができる。
【０１６９】
以下は、次のような3つのトークンを有する入力トークンシーケンスのクエリ統計スコアを決定する一例である。
ターム:北京(Beijing)、タイプ:市(City)
ターム:
【０１７０】
【数５７】
0005462361.tif 000058
【０１７１】
(Chaoyang)、タイプ:区(District)
ターム:
【０１７２】
【数５８】
0005462361.tif 000059
【０１７３】
(Datun Road)、タイプ:路(Road)
【０１７４】
まず、トークンシーケンスのタームクエリスコアが計算される。計算は、第1のトークン「北京(Beijing)、タイプ:市(City)」をカレントトークンとして定義し、カレントトークンのタームクエリスコアを決定することで始まる。すなわち、カレントトークンのタームユニグラム北京(Beijing)のクエリ統計スコアおよびカレントトークンのタームで始まるタームバイグラム
【０１７５】
【数５９】
0005462361.tif 000060
【０１７６】
(Beijing Chaoyang)を統計モデル250を参照することにより決定し、2つの結果として得られたクエリ統計スコアを比較し、高い方の1つ、例えば、クエリ統計スコア
【０１７７】
【数６０】
0005462361.tif 000061
【０１７８】
(Beijing Chaoyang)を、スコアST1と記されるカレントトークンのタームクエリスコアとして選択する。次に、トークン「ターム:
【０１７９】
【数６１】
0005462361.tif 000062
【０１８０】
(Chaoyan)、タイプ:District」がスキップされる。なぜなら、このトークンのタームが、ターム北京(Beijing)を伴うカレントトークンのタームクエリスコアを決定するときに考慮されているからである。ネクストトークンは、「ターム:
【０１８１】
【数６２】
0005462361.tif 000063
【０１８２】
(Datun Road)、タイプ:路(Road)」であり、これはカレントトークンのタームクエリスコアを決定するときには、考慮されていない。従って、トークン「ターム:
【０１８３】
【数６３】
0005462361.tif 000064
【０１８４】
(Datun Road)、タイプ:路(Road)」は、カレントトークンとして定義され、このカレントトークンのタームクエリスコアは、モデルの中に格納されるユニグラムタームのクエリ統計スコアとして決定され、スコアST2と記される。スコアST1は、スコアST2と合計され、結果が全タームシーケンス(全てのタームのシーケンス)
【０１８５】
【数６４】
0005462361.tif 000065
【０１８６】
(Beijing Chaoyang Datun Road)のクエリ統計スコアと比較されて、高い方の1つがトークンシーケンスのタームクエリスコアとして選択される。
【０１８７】
次に、入力トークンシーケンスのタイプクエリスコアが計算される。上述のように、トークンシーケンスの中の第1のトークン「ターム:北京、タイプ:City」がカレントトークンとして定義され、入力トークンシーケンスのタイプクエリスコアの計算がカレントトークン「北京(Beijing)、タイプ:市(City)」のタイプクエリスコアを決定することで始まる。すなわち、タイプユニグラム「City」およびカレントトークンのタイプを伴って始まるタイプバイグラム「City District」のクエリ統計スコアをモデル250を参照することにより決定し、取得されたクエリ統計スコアを比較して、高い方の1つ、例えば、クエリ統計スコア「City」、を第1のトークンのタイプクエリスコアとして選択し、これはスコアST3と記される。次に、ネクストトークン「ターム:
【０１８８】
【数６５】
0005462361.tif 000066
【０１８９】
(Chaoyang)、タイプ:区(District)」が、カレントトークンとして定義され、タイプユニグラム「District」およびタイプバイグラム「District Road」のクエリ統計スコアが統計モデル250を参照することにより決定され、高い方の1つが、例えば、タイプバイグラム「District Road」のクエリ統計スコアが、スコアST4と記される第2のトークンのタイプクエリスコアとして選択される。第3のトークンは、前のトークン「ターム:
【０１９０】
【数６６】
0005462361.tif 000067
【０１９１】
(Chaoyang)、タイプ:区(District)」のタイプクエリスコアを決定するときに考慮されていることから、スキップされる。スコアST3は、スコアST4と合計され、結果が全タイプシーケンス(全てのタイプのシーケンス)「City District Road」のクエリ統計スコアと比較され、高い方の1つがトークンシーケンスのタイプクエリスコアとして選択される。
【０１９２】
このとき、トークンシーケンスのタームクエリスコアおよびタイプクエリスコアは、一緒に加えられ、結果がトークンシーケンスのクエリ統計スコアになる。
【０１９３】
図2に戻ると、システム200のパーシングモジュール230は、入力エントリをロケーション部とクエリ部へとパーシングする。図6Aは、入力エントリをパーシングモジュール230によりパーシングする模範的な処理600Aを例示するフローチャートである。
【０１９４】
ステップS610で、入力エントリが受信され、例えば、トークン化モジュール210を使ってトークン化され、トークンシーケンスが取得される。入力エントリは、タイプでアノテートされたトークンのシーケンスへとトークン化される。上述のように、入力エントリは、ユーザによりクライアント端末210において入力され、パーシングモジュール230にネットワーク230経由で送信されてよい。
【０１９５】
随意的に、ステップS620で、事後処理を実行して、既定のタイプ修復ルールを使ってトークンシーケンスの中の明らかに誤ったタイプを修復することができる。タイプ修復ルールは、トークンにアノテートされた明らかに誤ったタイプを修復するためである。実装形態においては、ルールは、条件、および対象動作または対象値の、2つの部分により定義することができる。条件が満足された場合、対象動作が実行されるかまたは対象値が返される。例えば、タイプ修復ルールは、タイプ「数量サフィックス」を伴うトークンが、タイプ「Number」を伴うトークンに続かない場合は、タイプ「数量サフィックス」は、タイプ「None」へと変更されると規定できる。以前の例において述べたように、最初にアノテートされたタイトル
【０１９６】
【数６７】
0005462361.tif 000068
【０１９７】
(China Time-honored Brand Donglaishun)のターム「号」のタイプ「数量サフィックス」が、タイプ「None」へと変更される。なぜなら、ターム「号」は、「number」に対する漢字と同じものを使ってはいるが、ターム「号」は会社のブランド設定を表し、「由緒あるブランド(Time-honored Brand)」を意味するターム「老字」(Laozi)との組み合わせで使用される。
【０１９８】
ステップS630で、トークンシーケンスの中の2つの隣接するトークンの間の全ての位置に対して、その位置が分割の可能な位置ということがありうるかどうかを、例えば、既定の不分割ルールを使って、またもし、それが明らかに不可能な位置であれば除去することにより、決定する。不分割ルールは、分割すべき位置ではない位置を規定するためのものである。例えば、不分割ルールは、「街路」のタイプを伴うトークンと「Number」のタイプを伴うトークンの間の位置が、分割すべき位置ではないということを規定することができる。明らかに誤った分割位置を除去する動作は、統計モデル250におけるノイズの影響を低減することができる。
【０１９９】
ステップS640で、分割スコアが可能な分割方法ごとに計算される。分割スコアは、可能な分割方法の正しさについての統計的確率を示す。分割方法は、クエリ部およびロケーション部により定義される。それぞれの可能な分割方法は、1つの可能な分割位置に対応する。可能な分割位置は、トークンシーケンスを2つの部分に分割する、トークンシーケンスの中の2つの隣接するトークンの間の位置でありうる。可能な分割位置は同様に、トークンシーケンスを1つのサブ-トークンシーケンスに「分割」する、トークンシーケンスの第1のトークンの前または最後のトークンの後の位置でありうる。さらに具体的に言えば、トークンシーケンスの中の2つの隣接するトークンの間にあり、トークンシーケンスを2つの部分、すなわち2つのサブ-トークンシーケンス、に分割する可能な分割位置に関して、クエリ統計スコアおよびロケーション統計スコアが、例えば、図7A〜7Cおよび図8A〜8Cにおいて説明された処理を使って、これら2つのサブ-トークンシーケンスのそれぞれに対して決定される。サブ-トークンシーケンスのロケーション統計スコアは、サブ-トークンシーケンスがロケーション部である確率を示し、サブ-トークンシーケンスのクエリ統計スコアは、サブ-トークンシーケンスがクエリ部である確率を示す。可能な分割位置により分割される2つのサブ-トークンシーケンスの中で、より高いロケーション統計スコアを有する1つは、入力エントリの可能なロケーション部と見なされ、他の1つは入力エントリの可能なクエリ部と見なされる。対応する可能な分割のスコアは、この分割のロケーション部のロケーション統計スコアおよびこの分割のクエリ部のクエリ統計スコアに基づいて決定される。一例として、分割のスコアは、可能なロケーション部のロケーション統計スコアおよび可能なクエリ部のクエリ統計スコアを合計することにより決定される。その上、トークンシーケンスを1つのサブ-トークンシーケンスへと分割する可能な分割位置に関しては、ロケーション統計スコアおよびクエリ統計スコアが、全体のトークンシーケンスに対して決定される。この位置に対応する可能な分割方法は、全体のトークンシーケンスをロケーション部と見なすことにより決定され、および、全体のトークンシーケンスのロケーション統計スコアが全体のトークンシーケンスのクエリ統計スコアより高い場合は、分割スコアは全体のトークンシーケンスのロケーション統計スコアとして決定される。同様に、トークンシーケンスを1つのサブ-トークンシーケンスへと分割する位置に対応する可能な分割方法は、全体のトークンシーケンスをクエリ部と見なすことにより決定され、また、全体のトークンシーケンスのクエリ統計スコアが全体のトークンシーケンスのロケーション統計スコアより高い場合は、分割スコアは、全体のトークンシーケンスのクエリ統計スコアとして決定される。
【０２００】
随意的に、クエリ部のためのクエリ乗数およびロケーション部のためのロケーション乗数を含む2つの乗数を、クエリ部のクエリ統計スコアおよびロケーション部のロケーション統計スコアを調整するために決定することができる。可能な分割は、そのクエリ乗数およびロケーション乗数のうちのどちらかがゼロの場合は排除することができる。乗数は、以下のように決定することができる。まず、クエリ部のためのベースクエリ乗数およびロケーション部のためのベースのロケーション乗数を含む、2つのベース乗数が決定される。一実装形態においては、ベース乗数は、既定の値としてあらかじめ定義される。別の実装形態においては、ベース乗数は、これら2つの部分の項目および長さに基づいて決定される。ベース乗数は、そのまま、クエリ乗数およびロケーション乗数として使用されうる。代替的には、ロケーションベース乗数は、昇格する(promotion)か、または降格する(demotion)かにより調整し、調整されたロケーションベース乗数がロケーション乗数として使用されてもよい。例えば、ロケーション部のトークンシーケンスが、例えば［province + city + district + street］などの、階層順位におけるアドレス成分を包含する場合は、ロケーション乗数は、昇格されてよい。階層行政アドレス(例えば、city、district)の長さおよび階層一般アドレス(例えば、street、building)の長さが、計算されてよく、また重み付けされた値がロケーションベース乗数に加算されてよい。別の例としては、ロケーション部のトークンシーケンスが階層順位でないアドレス成分を包含する場合は、ロケーションベース乗数は降格される。さらに別の例としては、例えば「北京市  北京」などの、デュプリケートアドレス成分がトークンシーケンスの中にある場合は、ロケーションベース乗数は降格される。クエリ乗数およびロケーション乗数の決定後、クエリ部のクエリ統計スコアおよびロケーション部のロケーション統計スコアが、決定されたクエリ乗数およびロケーション乗数を使って調整される。具体的には、クエリ部のクエリ統計スコアが、クエリ乗数により乗じられ、ロケーション部のロケーション統計スコアが、ロケーション乗数により乗じられる。分割のスコアは、調整されたクエリおよびロケーション統計スコアを合計することにより決定することができる。
【０２０１】
随意的に、ステップS650で、優先度が、可能な分割のそれぞれに割り当てられる。2つのレベルの優先度が、使用されてもよく、また2つの数字1および0により表されてもよい。ここで、1は高い優先度、および0は低い優先度である。優先度は、以下のように割り当てられてよい。例えば、トークンシーケンスの中の2つの隣接するトークンの間の分割位置に対応する分割に関しては、この分割が、例えば空白、コンマなどのセパレータにより分割される場合は、分割の優先度は1である。そうでなければ、分割が、セパレータによって分割されるのでない場合は、分割の優先度は0である。全体のトークンシーケンスがクエリ部またはロケーション部である分割に対しては、入力エントリがセパレータを包含する場合は、分割の優先度は1、そうでなければ、分割の優先度は0である。
【０２０２】
ステップS660で、可能な分割はソートされ、最上位の可能な分割がパーシング結果として選択される。一実装形態においては、可能な分割は、分割スコアによりソートされる。優先度が可能な分割のそれぞれに割り当てられる別の実装形態においては、可能な分割は、まず優先度により、次にスコアによりソートされてもよい。上述のように、結果として得られた分割は、そのクエリ部およびロケーション部により表される。
【０２０３】
随意的に、ステップS670で、全体の入力エントリが可能なロケーションかどうかが決定される。入力エントリは、それが以下の条件:1)入力エントリがある特定の状態を満たす、例えば、入力エントリが数で終わる、2)全体のロケーション分割(すなわち、全体のトークンシーケンスがロケーション部である)が、2番目に高いスコアを伴う分割であり、そのスコアの最高の分割スコアに対する比率が、既定の閾値より高い、のいずれかを満たす場合は、可能なロケーションと決定される。全体の入力エントリが可能なロケーションであると決定されると、全体の入力エントリがロケーション部である分割は、参考として出力できる付加的な結果として得られた分割と見なされる。
【０２０４】
随意的に、ステップS680で、分割信頼スコア(splitting confidence score)が、結果として得られた分割ごとに決定される。分割信頼スコアは、分割の正しさの確かさを示す。一実装形態においては、分割信頼スコアは、以下のように定義される。まず、クエリ信頼スコアおよびロケーション信頼スコアが、項目(タームユニグラム、タームバイグラム、タイプNoneの隣接するタームのシーケンス、全てのタームのシーケンス、タイプユニグラム、タイプバイグラム、全てのタイプのシーケンスを含む)に対して、方程式(3)および(4)により定義される。
query_conf = query_score / (query_score + location_score)
...方程式(3)
location_conf = location_score / (query_score + location_score)
...方程式(4)
ここで、query_confおよびlocation_confは、それぞれ、項目のクエリ信頼スコアおよびロケーション信頼スコアであり、query_scoreおよびlocation_scoreは、それぞれ、項目のクエリ統計スコアおよびロケーション統計スコアである。次に、分割のクエリ部に対するクエリ信頼スコアは、クエリ部のタームクエリスコアを決定するために使用される、項目のクエリ信頼スコアの平均として定義され(図8B)、また分割のロケーション部に対するロケーション信頼スコアは、ロケーション部のタームロケーション信頼スコアを決定するために使用される、項目のロケーション信頼スコアの平均として定義される(図7B)。ある分割の分割信頼スコアは、この分割のロケーション部のロケーション信頼スコアと、この分割のクエリ部のクエリ信頼スコアとの平均として定義される。一例として、分割信頼スコアは、［0、1］の範囲内の値を有し、分割信頼スコアが高いほど、分割の正しさにおける信頼がある。分割信頼スコアは同様に、パーシングモジュール230により参考として出力することができる追加のパーシング結果である。
【０２０５】
図6Aを参照すると、ステップS690で、パーシング結果がパーシングモジュール230により出力される。このパーシング結果は、ステップS660で取得された、結果としての分割を含む。模範的な処理600Aにおいて、パーシング結果は、ステップS670および680で取得された追加の結果も同様に含み、これは、参考としてシステム200のユーザにより使用されうる。システム200のユーザには、システム200の結果を使用する、モジュール、コンポーネントまたはシステムが含まれる。例えば、マップサーチシステム140は、システム200のユーザの1つである。
【０２０６】
図6Aにおける上記の処理の種々の処理動作は、代替的処理により実装されうる。図6Bは、入力エントリをパーシングモジュール230によりパーシングする別の模範的な処理600Bを例示する、フローチャートである。処理600Bにおける処理ステップS610、640、660および690は、図6Aの処理600Aにおける同一の参照番号を伴うステップと実質的に同じである。
【０２０７】
マップサーチのために入力エントリをロケーション部およびクエリ部へとパーシングするための、図2のパーシングシステム200の種々の特性を、図2〜8Cに関して説明したが、以下の章では、パーシングシステム200の出力に基づくマップサーチを説明する。図1の例においては、マップサーチは、サーバ120において、パーシングシステム200およびマップサーチシステム140により実行される。
【０２０８】
図9はマップサーチを実行する模範的な処理を説明するフローチャートである。ステップS902で、入力エントリが、パーシングシステム200により受信される。入力エントリは、クライアント110においてユーザによりマップサーチインターフェースへと入力することができ、またパーシングシステム200へネットワーク130を介して送信することができる。ステップS904で、入力エントリは、パーシングシステム200によりパーシングされ、ロケーション部およびクエリ部の少なくとも1つを含むパーシング結果がマップサーチシステム140へと転送される。マップサーチシステム140は、パーシング結果に基づいてまたは参照して、マップサーチを実行する。一部の実装形態においては、マップサーチシステム140は、ステップS906で対象地理的領域(target geographic area)をロケーション部に基づいて決定する。例えば、マップサーチシステム140は、ロケーション部をジオコーディングして、対象地理的領域を得てもよい。対象地理的領域は、経度および緯度により定義されうる。ステップS908で、マップサーチシステム140は、対象地理的領域内のクエリ部により表される対象または複数の対象に関する情報を検索し、検索結果が、例えば、クライアント110に返され、ステップS910でユーザに提供される。
【０２０９】
図10は、本明細書の中に記載されたマップサーチのシステムおよび方法を実装するために利用することができる、模範的な装置1000のブロック図である。装置1000は、処理装置1002、第1のデータストア1004、第2のデータストア1006、入力装置1008、出力装置1010、およびネットワークインターフェース1012を含む。データバスおよびマザーボードを例えば含むバスシステム1014が、コンポーネント1002、1004、1006、1008、1010および1012の間のデータ通信を確立および制御するために使用されうる。他の模範的なシステムアーキテクチャも同様に使用されうる。
【０２１０】
処理装置1002は、例えば、1つまたは複数のマイクロプロセッサを含む。第1のデータストア1004は、例えば、ダイナミックランダムアクセスメモリ(DRAM)などのランダムアクセスメモリ(RAM)記憶装置、または他の種類のコンピュータ読み取り可能媒体メモリ装置などを含む。第2のデータストア1006は、例えば、1つまたは複数のハードドライブ、フラッシュメモリ、および/または読み出し専用メモリ(ROM)、または他の種類のコンピュータ読み取り可能媒体メモリ装置を含む。
【０２１１】
一部の実装形態においては、装置1000は、例えば第2のデータストア1006などのデータストアの中にコードを含む。コードは、実行されると処理装置1002に、パーシングシステム200および/またはマップサーチシステム140の機能を実行させる命令により定義されうる。例えば第2のデータストア1006などのデータストアは、辞書240および/または統計モデル250を格納することができる。
【０２１２】
模範的な入力装置1008は、キーボード、マウス、スタイラスなどを含み、模範的な出力装置1010は、ディスプレイ装置、オーディオ装置などを含む。一部の実装形態においては、入力装置1008は、統計モデル250を訓練するための訓練データを受信する。ネットワークインターフェース1012は、例えば、データを、例えば、ネットワーク130へおよびネットワーク130から伝えるように動作可能な、有線または無線のネットワーク装置を含む。ネットワークインターフェース1012は、入力エントリを遠隔装置から受信し、検索結果を遠隔装置に送信することができる。
【０２１３】
装置1000は、処理装置1002が、例えば第1のデータストア1004などのコンピュータ読み取り可能媒体に包含されるソフトウェア命令を実行することに応答して、本明細書の中に記載された特定の動作または処理を実行してもよい。コンピュータ読み取り可能媒体は、物理的または論理的メモリ装置および/または搬送波として定義されうる。ソフトウェア命令は、例えばディスク(disc)などの別のコンピュータ読み取り可能媒体から、または別の装置からネットワークインターフェース1012経由で、第1のデータストア1004へと読み込むことができる。第1のデータストア1004の中に包含されたソフトウェア命令は、処理装置1002に本明細書の中に記載された処理を実行させてもよい。
【０２１４】
実装形態においては、本明細書の中に記載された入力エントリをパーシングする処理およびマップサーチを実行する処理は、個別に、または他のマップサーチもしくはデータ処理技術と組み合わせて適用することができる。例えば、パーシングシステム200のパーシング結果は、入力エントリをパーシングまたは処理するための他のシステムからの追加の結果を同様に取得し、どちらの結果をマップサーチに用いるべきかを調停するシステムにより使用することができる。パーシングモジュール230により出力される分割信頼スコアは、調停のためのこの例のシステムにより使用することができる。別の例としては、マップサーチシステムは、本明細書の中に記載されたマップサーチ処理のみならず、他の技術を使う他のマップサーチ処理を実行して多数の検索結果を取得し、さまざまな処理の結果をユーザ配信するための最終検索結果に合成してもよい。
【０２１５】
本明細書の中に記載された主題の実施形態および機能的動作は、本明細書で開示された構造およびこれらの構造的な均等物、またはこれらの1つまたは複数の組み合わせを含むデジタル電子回路の中に、またはコンピュータソフトウェア、ファームウェア、またはハードウェアの中に実装することができる。本明細書の中に記載された主題の実施形態は、1つまたは複数のコンピュータプログラム製品、すなわち、データ処理装置による実行のための、またはデータ処理装置を制御するための有形のプログラムキャリア上にコード化された、コンピュータプログラム命令の1つまたは複数のモジュールとして実装することができる。有形のプログラムキャリアは、伝搬信号またはコンピュータ読み取り可能媒体でありうる。伝搬信号は、人工的に生成された信号、例えば、マシンにより生成された電気的、光学的、または電磁気的信号であり、この信号は、コンピュータによる実行のために適切な受信装置に送信するための情報をコード化するために生成される。コンピュータ読み取り可能媒体は、機械可読な記憶装置、機械可読な記憶装置基板、メモリ装置、機械可読な伝搬信号をもたらす物質の構成、またはこれらの1つまたは複数の組み合わせでありうる。
【０２１６】
「システム」という用語は、本明細書の中に記述された主題の機能を実行するための全てのシステム、装置、デバイス、およびマシンを網羅し、プログラム可能な1台のプロセッサ、1台のコンピュータ、または多数のプロセッサまたはコンピュータを例として含む。システムは、ハードウェアに加えて、問題のコンピュータプログラムに対する実行環境を生成するコード、例えば、プロセッサファームウェアを構成するコード、プロトコルスタック、データベース管理システム、オペレーティングシステム、またはこれらの1つまたは複数の組み合わせ含むことができる。
【０２１７】
コンピュータプログラム(プログラム、ソフトウェア、ソフトウェアアプリケーション、スクリプト、またはコードとしても知られる)は、コンパイルもしくはインタープリトされた言語、または宣言型もしくは手続き型言語を含む、プログラミング言語の任意の形態で書くことができ、また、スタンドアロンのプログラムとしてまたはモジュール、コンポーネント、サブルーチン、またはコンピュータ環境での使用に適している他のユニットとしてなどを含む、任意の形態で展開することができる。コンピュータプログラムは、ファイルシステムの中のファイルには必ずしも対応しない。プログラムは、他のプログラムまたはデータ(例えば、マークアップ言語ドキュメントの中に格納された1つまたは複数のスクリプト)を保持するファイルの一部分の中に、問題になっているプログラム専用の単一のファイルの中に、または多数の組織化されたファイル(例えば、1つまたは複数のモジュール、サブプログラム、またはコードの一部を格納するファイル)の中に、格納することができる。コンピュータプログラムは、1つのコンピュータ上または1つのサイトに位置する、または多数のサイトにわたって分散され通信ネットワークにより相互接続された多数のコンピュータ上で、実行されるように展開することができる。
【０２１８】
本明細書の中に記載された処理および論理の流れは、1つまたは複数のコンピュータプログラムを実行する1つまたは複数のプログラム可能なプロセッサにより実行されて、入力データに作用し出力を生成することにより、機能を実行することができる。処理および論理の流れは同様に、特殊用途の回路、例えば、FPGA(フィールドプログラマブルゲートアレイ)またはASIC(特定用途向け集積回路)により実行することができ、また装置もまた特殊用途の回路として実装することができる。
【０２１９】
コンピュータプログラムの実行に適しているプロセッサには、例として、一般的マイクロプロセッサおよび特殊用途のマイクロプロセッサの両方、ならびに任意の種類のデジタルコンピュータの任意の1つまたは複数のプロセッサが含まれる。一般に、プロセッサは、リードオンリーメモリもしくはランダムアクセスメモリまたは両方から命令およびデータを受信することになる。コンピュータの絶対不可欠な要素は、命令を実行するためのプロセッサおよび命令およびデータを格納するための1つまたは複数のメモリ装置である。一般に、コンピュータはまた、データを格納するための1つまたは複数の大容量記憶装置、例えば磁気ディスク、光磁気ディスク、または光ディスクなど、を含み、または、これらに動作可能に接続されて、データをこれらから受信またはデータをこれらに送信、または両方を行うことになる。しかしながら、コンピュータは、このような装置を有する必要はない。さらに、コンピュータは、例えば、少しだけ挙げると、携帯電話、携帯情報端末(PDA)、携帯オーディオまたはビデオプレーヤ、ゲーム機、全地球測位システム(GPS)受信器などの別の装置に内蔵されてもよい。
【０２２０】
コンピュータプログラム命令およびデータの格納に適しているコンピュータ読み取り可能媒体には、半導体メモリ装置、例えば、EPROM、EEPROM、およびフラッシュメモリ装置、磁気ディスク、例えば、内蔵ハードディスクまたは取り外し可能なディスク、光磁気ディスク、ならびにCDROMおよびDVDROMディスクを例として含む、全ての形態の不揮発性メモリ、媒体およびメモリ装置が含まれる。プロセッサおよびメモリは、特定用途ロジック回路により補完されるか、またはその中に組み込まれてもよい。
【０２２１】
ユーザとの対話を提供するために、本明細書の中に記載された主題の実施形態は、情報をユーザに表示するディスプレイ装置、例えば、CRT(陰極線管)またはLCD(液晶ディスプレイ)モニタ、ならびにキーボードおよびポインティングデバイス、例えば、マウスまたはトラックボール、を有するコンピュータ上に実装することができ、これらによりユーザがコンピュータに入力を提供することができる。他の種類の装置が、ユーザとの対話を提供するために同様に使用される。例えば、ユーザに提供されるフィードバックは、例えば、視覚的なフィードバック、聴覚的フィードバック、または触覚的フィードバックなどの感覚的フィードバックの任意の形態でありうる、またユーザからの入力は、音響的、会話的、または触覚性入力を含む、任意の形成で受信されうる。
【０２２２】
本明細書の中に記載された主題の実施形態は、バックエンドコンポーネントを、例えば、データサーバとして含むコンピュータシステム、または、例えばアプリケーションサーバなどのミドルウェアコンポーネントを含むコンピュータシステム、または、例えば、ユーザが、本明細書に記述された主題の実装形態と情報交換することができるグラフィカルユーザインターフェースまたはウエブブラウザを有するクライアントコンピュータなどのフロントエンドコンポーネントを含むコンピュータシステム、またはこのようなバックエンド、ミドルウェア、またはフロントエンドコンポーネントの1つまたは複数の任意の組み合わせを含むコンピュータシステムの中に実装することができる。システムのコンポーネントは、デジタルデータ通信の任意の形態すなわち媒体、例えば、通信ネットワークにより相互接続されうる。通信ネットワークの例には、ローカルエリアネットワーク(「LAN」)および広域ネットワーク(「WAN」)、例えば、インターネットが含まれる。
【０２２３】
コンピュータシステムはクライアントおよびサーバを含むことができる。クライアントおよびサーバは、一般に互いに離れており、また、典型的には通信ネットワークを通して対話する。クライアントとサーバの関係は、それぞれのコンピュータ上で作動し、かつ、互いにクライアントサーバ関係を有するコンピュータプログラムによって生じる。
【０２２４】
本明細書の中に記載されたマップサーチに関連する処理および動作の場所は、ユーザのマップサーチの実行に介在する単一のコンピュータネットワークまたは、接続されたコンピュータネットワークの中の、1つまたは複数の場所においてでありうる。ユーザのマップサーチのための入力エントリに応答して、マップサーチに関連する処理および動作の実行が、本明細書の中に記載されたパーシング動作の結果に基づくパーシング動作および検索動作を含む、マップサーチに関連する処理および動作のためのそれぞれのコンピュータプログラムにより、1つまたは複数のコンピュータにおいて始動または生起される。一例として、コンピュータ実装されるマップサーチ方法が提供されて、マップサーチのためのユーザからの入力エントリが、入力エントリに基づくマップサーチの実施に先立って、入力エントリの中の位置情報を表すロケーション部および入力エントリの中のロケーション部に関連する検索対象を表すクエリ部へとパーシングされることをもたらす。この方法は同様に、マップサーチの実施をもたらして、ロケーション部に基づいて地理的領域またはロケーションを取得し、また、クエリ部に関連し、かつ、取得された地理的領域またはロケーションの所に、中に、または近くに位置する1つまたは複数のエンティティに関する情報を検索する。
【０２２５】
本明細書は、多くの特定の実装形態の詳細を包含するが、これらは、いかなる発明またはクレームされる可能性のあるものの範囲を制限するものとしてではなく、むしろ、特定の発明の特定の実施形態に特有であってもよい特性の説明と解釈されるべきである。別々の実施形態との関連で本明細書の中に記載された特定の機能は、同様に、単一の実施形態の中に組み合わせて実装することもできる。逆に、単一の実施形態との関連で記述された種々の機能は同様に、多数の実施形態の中で個別にまたは任意の適切なサブコンビネーションの中に実装することができる。その上、機能は、上記では特定の組み合わせの中で作動するものとして記述されてもよいし、また初めはこのようなものとして請求されてさえもよいが、請求される組み合わせからの1つまたは複数の機能は、一部のケースにおいては、この組み合わせから削除することができ、また請求される組み合わせは、サブコンビネーションまたはサブコンビネーションの変形を対象としてもよい。
【０２２６】
同様に、動作は、特定の順序で図面の中に描かれているが、これは、望ましい結果を達成するために、このような動作が示された特定の順序で、すなわちシーケンシャルな順序に実行されること、または全ての例示された動作が実行されること、を要求しているものと理解されるべきではない。特定の状況においては、マルチタスクおよび平行処理が有利な可能性がある。さらに、上述の実施形態における種々のシステムコンポーネントの分離は、全ての実施形態においてこのような分離を要求していると理解されるべきではなく、また、記述されたプログラムコンポーネントおよびシステムは、全体として単一のソフトウェア製品に統合されるかまたは多数のソフトウェア製品へとパッケージ化されうるということが理解されるべきである。
【０２２７】
マップサーチシステムの特定の実施形態、装置および方法が説明された。説明された実施形態および他の実施形態の変形および強化は、本明細書の中で記載されているものに基づいてなされうる。例えば、ここで説明された行為は、異なる順序で実行されて、依然として望ましい結果を達成することができる。一例として、添付の図の中に描かれた処理は、望ましい結果を達成するために、示された特定の順序、すなわちシーケンシャルな順序を必ずしも要求しない。特定の実装形態においては、マルチタスクおよび並列処理が有利な可能性がある。
【符号の説明】
【０２２８】
110  クライアント
120  サーバ
130  ネットワーク
140  マップサーチシステム
200  パーシングシステム
210  トークン化モジュール
220  モデル訓練モジュール
230  パーシングモジュール
240  辞書
250  統計モデル
1002  処理装置
1004  第1のデータストア
1006  第2のデータストア
1008  入力装置
1110  出力装置
1012  ネットワークインターフェース
【図１】
0005462361.tif 000069
【図２】
0005462361.tif 000070
【図３】
0005462361.tif 000071
【図４】
0005462361.tif 000072
【図５】
0005462361.tif 000073
【図６Ａ】
0005462361.tif 000074
【図６Ｂ】
0005462361.tif 000075
【図７Ａ】
0005462361.tif 000076
【図７Ｂ】
0005462361.tif 000077
【図７Ｃ】
0005462361.tif 000078
【図８Ａ】
0005462361.tif 000079
【図８Ｂ】
0005462361.tif 000080
【図８Ｃ】
0005462361.tif 000081
【図９】
0005462361.tif 000082
【図１０】
0005462361.tif 000083