データサニタイゼーション及び正規化及びジオコーディング方法

著者らは特許

G06F17/30 - 情報検索;そのためのデータベース構造
G09B29/006 - 帯状のもの,例.無端帯
G09B29/10 - 地点指示スポットまたは座標による位置指示器;地図の読取り補助具

の所有者の特許 JP2016528553:

ザグ ホールディングス インコーポレーテッド

 

本技術の実施形態は、データサニタイゼーション及び正規化、並びにこれを適用したジオコーディング方法に関する。例示的な方法は、ジオデータセットをサニタイジングするステップと、正規化されたレーベンシュタイン距離アルゴリズムを用いて、サニタイジングされたジオデータを正規化するステップを含む。
【選択図】図1

 

 

関連出願
本出願は、2013年8月14日に出願された米国仮出願番号第61/865,984号、発明の名称「Systems and Methods for Geocoding and Correcting Geocoded Data」の優先権を主張し、この文献は、その内に記載されている全ての引用文献を含み、その全体が引用によって本明細書に援用される。
本技術の分野
本技術は、包括的には、ジオコーディング(geocoding)及び地図作成に関し、詳しくは、以下に限定されるわけではないが、各関心点が異なるデータベースとの間で一貫性を欠く複数の表現によって表されている際に、関心点を正しくジオコーディングするシステム及び方法に関する。本技術は、これらの一貫性を欠く表現を調和させて、これらのジオコーディングされた位置の一貫性を向上させる。
本技術の実施形態は、方法を含み、この方法は、(a)それぞれがフォーマットを有する複数のセグメントをそれぞれ有する2つのマルチセグメント文字セットを受信するステップと、(b)(i)セグメントのフォーマットが標準化されたフォーマットでない場合、マルチセグメント文字セットの複数のセグメント内のセグメントを標準化されたフォーマットに変換し、(ii)変換されたセグメント及び変換されていないセグメントから連続する文字列を作成することによって、2つのマルチセグメント文字セットのそれぞれを短縮することによって、2つのマルチセグメント文字セットのそれぞれをサニタイジングするステップと、(c)サニタイジングされたマルチセグメント文字セットを用いて、サニタイジングされたマルチセグメント文字セットの文字間の差を表す距離スコアを算出するステップとを有する。
本技術の他の実施形態は、演算デバイスを含み、この演算デバイスは、(a)実行可能な命令を保存するメモリと、(b)実行可能な命令を実行して、(i)それぞれがフォーマットを有する複数のセグメントをそれぞれ有する2つのマルチセグメント文字セットを受信し、(ii)(1)セグメントのフォーマットが標準化されたフォーマットでない場合、マルチセグメント列の複数のセグメント内のセグメントを標準化されたフォーマットに変換し、(2)変換された複数のセグメントから連続する文字列を作成することによって、2つのマルチセグメント文字セットを短縮することによって、2つのマルチセグメント文字セットをサニタイジングし、(iii)サニタイジングされたマルチセグメント文字セットについて正規化されたレーベンシュタイン距離(NLD)を算出するプロセッサとを備え、正規化されたレーベンシュタイン距離は、(A)サニタイジングされたマルチセグメント文字セットについてのレーベンシュタイン距離(LD)を算出し、(B)以下の式を用いてLDを正規化することによって算出され、
NLD=1−(LDexp1−abs([LSexp1]−[LSexp2]))/min([LDexp1],[LSexp2])
ここで、LSexp1は、サニタイジングされたマルチセグメント文字セットの第1の文字列の長さであり、LSexp2は、サニタイジングされたマルチセグメント文字セットの第2の文字列の長さである。
本技術の更なる実施形態は、ジオコーディング方法を含み、この方法は、(a)それぞれがフォーマットを有する複数のセグメントをそれぞれが有し、同じ関心点を表現する可能性がある2つのマルチセグメント文字セットを受信するステップと、(b)セグメントのフォーマットが標準化されたフォーマットでない場合、マルチセグメント列の複数のセグメント内のセグメントを標準化されたフォーマットに変換するステップと、(c)変換されたセグメント及び変換されていない複数のセグメントから連続する文字列を作成することによって、2つのマルチセグメント文字セットのそれぞれを短縮するステップと、(d)サニタイジングされたマルチセグメント文字セットを用いて、サニタイジングされたマルチセグメント文字セットの文字の差を表す距離スコアを算出するステップと、(d)距離スコアを閾値と比較するステップと、(e)距離スコアが閾値を下回る場合、データベースにおいて、サニタイジングされたマルチセグメント文字セットが、同じ関心点を表していると特定するステップとを有する。
本技術の側面を実現するためのコンピューティング環境の高レベル概略図である。 ジオコーディング処理を例示する概要及びフローチャートである。 同じ物理的な関心点を表す2つのジオコーディングされた点の間の物理的距離計算の処理を説明する地図を示す図である。 本技術の方法のフローチャートである。 正規化されたレーベンシュタイン距離計算及び物理的距離計算を実行する方法のフローチャートである。 ジオデータインスタンスのセグメント/フィールドの順列を作成及び使用する方法のフローチャートである。 本技術に基づく実施形態を実現するために使用されるコンピュータシステムの概略図である。
以下では、本発明の完全な理解のために、限定ではなく説明を目的として、例えば、特定の実施形態、手順、技術等を具体的詳細に述べる。しかしながら、本発明は、これら具体的詳細とは異なる他の実施形態において実現してもよいことは、当業者にとって明らかである。
本明細書における「一実施形態」又は「実施形態」という表現は、その実施形態に関連して記述される特定の特徴、構造又は特性が、本発明の少なくとも1つの実施形態に含まれることを意味する。したがって、明細書の様々な箇所で用いる「一実施形態において」又は「実施形態において」又は「実施形態によれば」といった表現(又は同様の趣旨の語句)は、全てが必ずしも同じ実施形態について言及しているというわけではない。更に、1つ以上の実施形態において、適切な何らかの手法で、特定の特徴、構造又は特性を組合せてもよい。更に、この説明の文脈に応じて、単数形の語句は、複数の意味も含み、複数形の語句は、単数の意味も含むことができる。同様に、ハイフンで接続した語句(例えば、「(on-demand)」)は、場合に応じて、ハイフンがない同じ語句(例えば、「on demand」)と交換可能に使用してもよく、先頭を大文字にした語句(例えば、「Software」)は、先頭を大文字にしていない同じ語句(例えば、「software」)と交換可能に使用でき、複数語は、アポストロフィの有無を問わず(例えば、PE's又はPEs)、そして、イタリック体の語(例えば、「「N+1」(イタリックフォント)」)は、非イタリック体のバージョン(例えば、「N+1」(標準フォント))と交換可能に使用できる。このような場合に応じた交換可能な使用は、互いに一貫性を有していないとはみなされないものとする。
また、幾つかの実施形態は、タスク又は一組のタスクを実行する「手段」に関して記述することがある。「手段」とは、例えば、プロセッサ、メモリ、カメラ等の入出力装置又はこれらの組合せに関する構造の表現であってもよい。これに代えて、「手段」は、機能又は方法のステップを記述するアルゴリズムを含んでもよく、更に他の実施形態においては、「手段」は、数式(formula)や記述(prose)に関連して表現してもよいし、又は、フローチャートや信号図として表現してもよい。
本明細書中の用語は、特定の実施形態を記述することを目的とし、本発明を制限する意図はない。ここで使用する、不定冠詞及び定冠詞が付された単数名詞は、文脈上、明確に他を示すものでない限り、複数も包含するものとする。更に、本明細書で使用する「備える」、及び/又は「有する」等の表現は、記述した特徴、値、ステップ、動作、要素及び/又は成分の存在を特定するものであり、これ以外の特徴、値、ステップ、動作、要素、成分及び/又はこれらのグループの存在又は追加を除外する意図はない。
なお、ここで用いる「接続(coupled, connected, connecting)」、「電気的に接続(electrically connected)」といった用語は、本明細書において交換可能に用いられ、電気的/電子的に接続される状態を包括的に意味する。同様に、信号のタイプ(アナログ又はデジタル)を問わず、第1のエンティティが第2のエンティティに情報信号(データ情報又は非データ/制御情報を含むかを問わず。)を電気的に送信及び/又は受信(有線手段を介するか又は無線手段を介するかを問わず。)している場合、第1のエンティティは、第2のエンティティ(又は複数のエンティティ)と「通信」しているとみなす。更に、本明細書で示し説明する様々な図面(ブロック図を含む。)は、例示のみを目的とし、実際の縮尺を反映していない。
関心点を表すソースデータ表現は、誤っていることがあり、及び/又は完全な情報が不足することがあるので、ジオコーディングは、不正確な処理になることも多い。この誤ったソースデータによって、関心点は、地図上で誤ってプロットされ、これによって、地図のエンドユーザに不都合が生じ、地図提供者が信頼を失う可能性がある。
特徴の位置マッピングの一貫性及び利便性を維持するために、地図上で関心点を正しくプロットすることが重要である。経験上、全ての関心点(例えば、ホテル)の25%は、誤ってプロットされているとされている。例えば、これらのホテルは、正しい位置から1マイル以上離れてプロットされていることもある。このようなことが生じるのは、ホテルのジオロケーションデータ(以下、「ジオデータ」)が不完全であり、誤っており、又はフォーマットが不十分であるためである。更に、マッピングシステムは、複数の異種のデータベースに依存することが多く、各データベースは、それぞれ異なるフォーマットを用いて関心点を定義することがある。例えば、1つのホテルデータベースがホテルのアドレスを「20 5th Avenue West, New York」としてフォーマット化し、他のホテルデータベースが全く同じホテルのアドレスを「20 Fifth Ave., W. newyork」としてフォーマット化することがある。これらのアドレスは、同じ位置の同じホテルを指しているが、地図上でホテルをプロットする際、アドレスのフォーマットによってエラーが導入される可能性がある。
本技術は、ジオデータサニタイゼーション、距離及び正規化処理によって、これらの問題を解決することができるという利点を有する。なお、本技術をジオデータのコンテキストで説明するが、ここに開示するサニタイゼーション及び正規化処理は、データフォーマットの調和を必要とする任意のデータ処理方法にも適用できる。例えば、入力データが様々なフォーマットで提供されることに影響を受けやすく、このため、入力データが適用される際にエラーが生じるおそれがある場合に本技術を用いることができる。
本技術は、検証及び再フォーマット化が必要な関心点を特定することによってジオコーディング処理を改善する。本技術は、本明細書に記述するジオデータフォーマット方法を用いて、関係性を有さないデータベースからの関心点を一致させ、関係性を有さないデータベースから提供されたジオデータをマッピングロジックを用いて統合し、プロット精度を向上させる。また、本技術は、新しい関心点を正確にプロットする。このように、本技術の幾つかの実施形態は、ジオコーディング並びに地図作成の技術を向上させ、特に、以下に限定されるわけではないが、本技術の実施形態に基づいてサニタイジングされ、正規化されたジオデータを用いて関心点をマッピングする。図面全体(図1〜図7)を参照して、本技術のこれら及びこの他の利点を以下に説明する。
図1は、本技術のコンピューティング構造(以下、アーキテクチャ100)の高レベル概略図である。アーキテクチャ100は、データサニタイゼーション及び正規化システム(以下、「サーバ105」)、第1のジオデータソース110、第2のジオデータソース115、ネットワーク120及びフォーマット化されたジオデータデータベース125を備える。
サーバ105、第1のジオデータソース110及び第2のジオデータソース115は、ネットワーク120を介して互いに通信可能に接続されている。ネットワーク120は、適切な任意の私有の又は公の通信ネットワークを含んでいてもよい
サーバ105は、通常、例えば、第1のジオデータソース110及び第2のジオデータソース115等の複数のジオデータソースからジオデータを受信する。これより多くのジオデータソースが含まれていてもよい。これらのジオデータソースのそれぞれは、様々な関心点(points of interest:POI)を表すジオデータインスタンスをサーバ105に提供することができる。例えば、第1のジオデータソース110及び第2のジオデータソース115は、ホテルの予約を提供するウェブサイトに関連する旅行サービスデータベースであってもよい。これらのジオデータソースは、ホテルが所有する専用のホテルデータベースであってもよい。
ジオデータインスタンス110A〜N等のジオデータインスタンスは、任意の数の情報フィールドを含んでいてもよい。ジオデータは、例えば、POI名、番地、都市、州、地方、郵便番号、電話番号、ファックス番号、ウェブサイト/領域/URL(ユニフォームリソースロケータ)、緯度及び経度等の座標をはじめとする情報フィールド並びにこれらの情報フィールドの組合せを含むことができる。当業者に知られている他の情報フィールドも本技術において使用することができる。幾つか実施形態では、ジオデータのフィールドは、セグメントと呼ばれる。すなわち、ジオデータのインスタンスは、複数のセグメント(例えば、複数のフィールド)を有することができる。
ジオデータは、ファイル、データベースエントリ、タブで区切られたファイル、コンマで分離された値のファイル、又は他の類似したデータ構造としてデータベースに保存することができる。上述したように、異なるソースからの同じ関心点についてのジオデータは、互いに一貫性を有していないことがあり得る。例えば、1つのジオデータインスタンスでは、番地(street address)が「145th St.」として特定され、他のジオデータインスタンスでは、同じ番地が「145 Street」として特定される等、幾つかのフィールドが異なるフォーマットを有していることがある。幾つか例では、ジオデータフィールドが誤っていることがあり得る。例えば、関心点の都市が、実際には「Menlo Park」であるのに、「Palo Alto」と誤記されていることもある。また、言語の不一致がジオコーディングを誤らせることもある。例えば、番地が、1つのジオデータインスタンスでは、「123 Avenida」とされ、他のジオデータインスタンスでは、「123 Avenue」とされることがある。この言語の違いによって、マッピング機能が言語差を補償することができない場合、関心点が誤ってプロットされることがある。
幾つかの実施形態においては、サーバ105が取得するジオデータは、まず、ジオデータ内の関心点(POI)を判定することによって処理される。サーバ105は、ジオデータソースから得られるジオデータから、例えば、番地、都市、州、郵便番号等のアドレスフィールドを取得する。サーバ105は、アドレスフィールドを使用して、地図上にPOIをプロットする。
そして、サーバ105は、POIアドレスの潜在的正確度(potential accuracy)を判定し、更に、互いに一致する任意のPOIアドレスを選択する。幾つかの実施形態においては、サーバ105は、地図上にプロットされるPOIアドレスの間の距離を計算することによってPOIアドレスの正確度を判定する。また、サーバ105は、第1のジオデータソース110及び第2のジオデータソース115の初期正確度評価(initial accuracy rating)も考慮する。すなわち、幾つかの具体例では、第1のジオデータソース110及び第2のジオデータソース115のそれぞれは、そのジオデータソースが提供しているジオデータがどれほど正確かを表す正確度値をサーバ105に提供する。幾つかの具体例では、サーバ105は、第1のジオデータソース110及び第2のジオデータソース115によって提供される正確度値が正しくないと判定した場合、これらの正確度値を参考にしなくてもよい。
POIアドレスは、緯度及び経度情報を含む座標データベースと比較することによって検証することができる。幾つかの具体例では、POIアドレスが、座標を含んでいてもよく、これらのジオデータ座標を座標データベース内の座標と比較して、POIアドレスの正確度を判定することができる。例えば、POIアドレスが「1234 Main Street」であり、緯度37、経度−132である場合、サーバ105は、この座標を座標データベースで調べ、POI番地を座標と比較して、POI番地が座標に実質的に対応するかを確認することができる。POI番地及び座標は、これらの2点が地図上にプロットでき、これらの間の距離が無視できる程度であるとき、実質的に対応する。例えば、地図のユーザが地図を使用して、誤った位置に案内されない場合、この距離は無視できる程度であるとみなされる。幾つかの具体例では、この距離の精度(granularity)及び近さ(closeness)は、位置によって判定できる。例えば、POIが多くの一方通行を有する人口密度が高い都市部にある場合、ユーザが間違った通りを進み、間違った位置に案内される可能性を低減するために、この距離は、より短い必要がある。一方、POIが人口過疎地域にあり、エンドユーザを混乱させる可能性がある隣接位置がない場合、この距離は、より長くてもよい。
何れの場合も、地図システム管理者は、この距離に閾値を設定することができる。距離が閾値より長い場合、POIには、不正確を示すフラグを付してもよく、サーバ105による再コーディングが必要であるというフラグを付してもよい。これにより、サーバ105は、ジオデータソースにジオデータを再コーディングするよう要求することができる。これに代えて又はこれに加えて、幾つかの実施形態においては、サーバ105がPOIのためのジオデータを無視してもよく、削除してもよい。
また、図1及び図2に示すように、サーバ105は、同じPOIに関するジオデータの複数のインスタンスを管理するように構成されている。POIの重複は、複数のデータソースが同じPOIに関するジオデータを提供した場合に生じる。上述のように、複数のホテル予約システムが、これらのホテルPOIジオデータをサーバ105に提供できる。地図上でこれらのホテルPOIジオデータインスタンスを表示するために、サーバ105は、比較及び/又は調和化(harmonization)を行う。
幾つかの実施形態では、サーバ105は、少なくともプロセッサ150及びメモリ155を備える。メモリ155は、サニタイゼーションモジュール160、距離モジュール165及びプロッティングモジュール175を包括的に含む。
プロセッサ150は、メモリに保存されているサニタイゼーションモジュール160を実行して、様々な動作を実行する。1つの実施形態においては、サニタイゼーションモジュール160は、ジオデータのインスタンスをフィールドに分けるように構成される。なおジオデータのインスタンスは、包括的に、マルチセグメント文字セット(multi-segment set of characters)と呼ばれる場合もある。例えば、ジオデータのインスタンスは、「Hotel Mainstreet, 1234 Main St., Anytown, State, USA, 99991, (34, -123)」を含むことがある。上述のように、ジオデータは、任意のフォーマットを有していてもよい。例えば、ジオデータは、列又は行スタイルのリスト、コンマで分離された一組の値、タブで区切られた一組のフィールド又は他の適切な任意のフォーマットに配列されたフィールドを含むことができる。サーバ105は、ジオデータのインスタンスを別々のフィールド、例えば、「Name=Hotel Mainstreet; StreetAddress=1234 Main St.; City=Anytown; State=State; Country=USA; Zipcode=99991; Latitude=34; Longitude=-123」に分けてもよい。
幾つかの実施形態において、サニタイゼーションモジュール160は、ジオデータのインスタンス内の全ての大文字を小文字に変換する。また、サニタイゼーションモジュール160は、ジオデータのインスタンスから全ての非英数字を除去する。非英数字の除去によって、フィールドを1つの文字列に連結し又は短縮することができる。
そして、サニタイゼーションモジュール160は、例えば、フィールドサニタイザ(field sanitizer)モジュール180A〜N等の複数の特定用途サニタイザ(special purpose sanitizers)を用いて、ジオデータのインスタンスのフィールドを処理してもよい。包括的に言えば、サニタイゼーションモジュール160は、セグメントのフォーマットが標準化されたフォーマットでない場合、セグメント又はフィールドを標準化されたフォーマットに変換するように構成されている。フィールドサニタイザモジュール180A〜Nの以下の例は、同じPOIを表すジオデータの矛盾したフィールドを調和させるために、フィールドを標準的なフォーマットに変換するのに用いられる。
フィールドサニタイザモジュール180A〜Nの数は、ジオデータのインスタンスに存在するフィールドの数に依存する。フィールドサニタイザモジュール180A〜Nのそれぞれは、特定の種類のジオデータフィールドをサニタイジングするように構成されている。例えば、名称フィールドサニタイザモジュール180Aは、ジオデータのインスタンスの名称フィールドをサニタイジングする。ある具体例においては、名称フィールドが単語「hotel」若しくは「inn」又は例えば、「motel」等の他の類似した語を含まない場合、名称フィールドサニタイザモジュール180Aは、名称フィールドに「hotel」という語を入れる。すなわち、名称フィールドについて標準化されたフォーマットは、名称フィールドに「hotel」という語が存在することを要求する。番地フィールドサニタイザモジュール180Bは、ジオデータのインスタンスの番地フィールドを正規化するように構成されている。例えば、番地フィールドサニタイザモジュール180Bは、「Avenida」、「Avenue」及び「Av」等のフィールドデータを、「ave」に置換することができる。したがって、「ave」は標準化されたフォーマットである。他の例として、「Four」、「Fourth」、「4th」、「IV」、「quatre」及び「cuatro」は、全て「4」の標準化されたフォーマットに変更される。このように、各種の番地データに対し、標準化されたフォーマットが適用され、多くの異なるフォーマットが標準化されたフォーマットに正規化される。
1つの非限定的な例では、ジオデータの第1のインスタンスは、「20 5th Avenue West, New York」の番地フィールドを含み、これは、「205avewnewyork」に変換される。大文字は、小文字に変更され、非英数字、例えば、スペース及びコンマは、取り除かれる。そして、番地フィールドは、「5th」を「5」に、「avenue」を「ave」に、「west」を「w」に変更するように処理される。
他の例では、ジオデータの第2のインスタンスは、「20 Fifth Ave., W., newyork」の番地フィールドを含み、これは「205avewnewyork」に変換される。大文字は、小文字に変更され、スペース及びコンマのような非英数字は、取り除かれる。そして、1つの番地フィールドは、「Fifth」を「5」に変更するように処理される。
この例では、ジオデータの第1のインスタンスは、第1のジオデータソース110に由来し、ジオデータの第2のインスタンスは、第2のジオデータソース115に由来していてもよい。
都市、州及び国名も同様の手法で、それぞれのフィールド正規化モジュールを用いてサニタイジングできる。サニタイゼーション/正規化の後、サニタイジングされたアドレスフィールド及び都市フィールドは、サーバ105によってジオコーディングエンジン170に供給され、ジオコーディングエンジン170は、ジオデータのインスタンスの間で、可能な一致を特定する。ジオコーディングエンジン170は、サーバ105に統合してもよく、又は、幾つかの実施形態は、1つ以上のサードパーティのジオコーディングエンジンを含んでいてもよい。
別の例では、サニタイジングされたアドレス及び都市を、例えば、仮想個人名別電話帳又は仮想職業別電話帳等のローカルディレクトリエンジン185に供給して、サニタイジングされたアドレスが、ローカルディレクトリエンジン185内のリストに関連性を有しているかを判定してもよい。
1つの実施形態においては、距離モジュール165は、サニタイジングされたジオデータの2つのインスタンスの間のレーベンシュタイン距離(Levenshtein distance:LD)を算出する。通常、レーベンシュタイン距離は、2つの文字列の間で算出される。当業者は、サニタイジングされた一対のジオデータ文字列について、LDを算出することができる。一般に、LDは、第1の文字列を変形して第2の文字列に対応付けるために、第1の文字列において幾つの置換が必要かを表す数値である。レーベンシュタイン距離は、幾つか単純な上限及び下限を有する。これらは、(a)LDは、常に少なくとも2つの文字列のサイズの差であること、(b)LDは、多くても長い方の文字列の長さであること、(c)文字列が等しい場合に限り、LDはゼロであること、(d)文字列が同じサイズである場合、ハミング距離がLDの上限であること、(e)2つの文字列の間のLDは、第3の文字列に対するそれぞれのLDの合計を超えないこと(三角不等式)を含む。
例えば、第1のサニタイジングされた文字列は、「100 Avenida de Republica, Madrid」からサニタイジングされた「100avedereublicamadrid」を含み、第2のサニタイジングされた文字列は、「100 Republica Avenue, Madrid」からサニタイジングされた「100republicaavemadrid」である。
「100 Avenida de Republica, Madrid」と「100 Republica Avenue, Madrid」の間のLDは、17であり、これは、「100 Republica Avenue, Madrid」に至るまでに「100 Avenida de Republica, Madrid」に17回の置換を行う必要があることを意味する。第1及び第2のサニタイジングされた文字列のためのLDexp1も算出でき、これは、9であり、これは、「100republicaavemadrid」にいたるまでに「100avedereublicamadrid」に9回の置換を行う必要があることを意味する。
なお、距離モジュール165が、2つのジオデータインスタンスからの類似したフィールドタイプを比較又は照合することに注目すべきである。例えば、距離モジュール165は、第1のジオデータインスタンスの番地フィールドを第2のジオデータインスタンスの番地フィールドと比較する。フィールドタイプを考慮せずにフィールド間の比較を行うと、距離モジュール165による比較の結果が劣化するおそれがある。
距離モジュール165は、まず、第1のサニタイジングされた文字列の長さ(22である)と判定し、次に第2のサニタイジングされた文字列の長さ(21である)と判定することによって、LDexp1値を正規化する。
これらの長さ値を判定した後に、距離モジュール165は、以下の式を用いて正規化されたLD(normalized LD:NLD)値を算出する。
NLD=1−(LDexp1−abs([LSexp1]−[LSexp2]))/min([LDexp1],[LSexp2]) [式1]
ここで、LSexp1は、サニタイジングされたマルチセグメント文字セットの第1の文字列の長さであり、LSexp2は、サニタイジングされたマルチセグメント文字セットの第2の文字列の長さであり、LDexp1は、サニタイジングされた対について算出されたLDである。距離モジュール165の出力は、距離モジュール165によって比較された一対のジオデータのインスタンスのそれぞれのNLDスコアである。
詳しくは、距離モジュール165は、第1の文字列の長さから第2の文字列の長さを減算し、この値をLDexp1及び第2の文字列の長さの最小値によって除算する。この結果としての値の絶対値を求め、1から減算する。この絶対値をLDexp1から減算する。そして、距離モジュール165は、この最終的な数値に100を乗算して、NLDを得る。上述の例では、第1及び第2のサニタイジングされた文字列のNLDは、61.9%である。
幾つかの実施形態においては、距離モジュール165は、ジオデータインスタンスのセグメント/フィールドの様々な順列についてのNLD値を算出してもよい。上述の例で説明を続けると、アドレスフィールドの順列(単語の順序の変化)は、「100 de Reublica Ave, Madrid」と「100 Republica Ave, Madrid」を含む。サニタイジングされたバージョンは、「100dereublicaavemadrid」と「100republicaavemadrid」である。式1を使用すると、このジオデータインスタンスの対について90.1%のNLD値が算出される。ジオデータインスタンスから抽出したフィールドの再編成(rearrangement)によって、多くの異なる種類の順列を実現できる。一実施形態においては、距離モジュール165は、ジオデータインスタンス間の一致する単語の対毎の整列(pairwise alignment)を実行することができる。対毎の整列により、結果として生じるサニタイジングされた文字列について算出されるLDが小さくなる。距離モジュール165は、ジオデータインスタンスのフィールドの可能な全ての順列についてNLD値を算出し、最高ランクのNLD値を判定することができる。
この場合も、順列処理は、フィールドの下位部分が再編成されるように、フィールドの又はセグメントのレベルで行ってもよい。例えば、「100 Ave de Reublica, Madrid」は、「100 de Reublica Ave, Madrid」又は「100 Reublica de Ave, Madrid」に再編成してもよい。
図6を参照して、ジオデータインスタンスのセグメント/フィールドの順列を作成及び使用する処理の例示的なフローチャートのより詳細な説明を以下で行う。
幾つかの実施形態においては、距離モジュール165は、NLD閾値を適用することができ、NLDがNLD閾値を超えた場合、第1及び第2のサニタイジングされた文字列が同じPOIに対応するとみなす。例えば、NLD閾値は、80%であってもよい。これにより、NLDが80%より低ければ、ジオデータインスタンスは、同じPOIを表している可能性が低いと判定される。NLDが80%未満であっても、ジオデータインスタンスが実際に同じPOIを表していることもあり、ジオデータインスタンスは、最終的な判定を行うために地図プロッティング又は人間による確認を要求してもよい。第1及び第2のサニタイジングされた文字列が取得されるところの、ジオデータインスタンスは、更なる確認のためにフラグを付すことができる。また、サーバ105は、これらのデータのフォーマット及び/又はコンテンツに誤りがある可能性があることを各ジオデータソースに警告してもよい。NLD閾値は、要求される任意の感度に設定してもよい。
上述の例では、80%のNLD閾値の使用を想定しているが、このNLD閾値は、単なる例であり、NLD閾値は、望ましい任意の値に設定してもよく、システムのエンドユーザは、ジオデータインスタンスを比較するために望ましい感度レベルを決定することができる。
他の具体例では、第1のサニタイジングされた文字列である「sheratonhotel」と、第2のサニタイジングされた文字列である「sheratonhoteldowntowntoronto」について、NLDを算出する。この具体例では、LDは15であり、文字列が全く類似していないことを示すが、NLDは、サニタイジングされた文字列が同一であって、それぞれが同じPOIを表すことを示す100%が算出される。LDが第1及び第2の文字列の間の大きな距離的相違を示していても、NLD式は、式1を用いて第1及び第2の文字列の最小値をとる際、第2の文字列内の余分な文字を基本的に無視する。
このように、本技術は、一般的なLD計算の使用に対し、様々な目的のために使用できる正規化されたLDを用いることによる利点を提供し、すなわち、通常、一貫性が大きく欠ける(例えば、距離が大きい)文字列が同じコンテンツを表していることを特定することができる。ある例では、コンテンツは、ジオデータを含むが、他のコンテンツは、複数のフィールド(例えば、セグメント)によって表現される如何なるデータのタイプであってもよい。
幾つかの実施形態においては、距離モジュール165は、NLDが80%未満である場合、2つのサニタイジングされたアドレスの間で物理的距離チェックを実行することができる。例えば、距離モジュール165は、プロッティングモジュール175と連携して、2点の間の物理的距離を判定することができる。プロッティングモジュール175は、地図上に第1のサニタイジングされたアドレスと第2のサニタイジングされたアドレスをプロットする。距離モジュール165は、第1及び第2のサニタイジングされたアドレス間の物理的距離を算出することができる。例えば、距離モジュール165は、地図上の2つのプロットされた点の間の地理的距離を算出することができる。
物理的距離が100フィート未満である場合、距離モジュール165は、NLDが閾値以下であっても、第1及び第2のサニタイジングされたアドレスが同じPOIを表しているとみなす。上述の例に戻って説明すると、第1のサニタイジングされた文字列である「100avedereublicamadrid」と、第2のサニタイジングされた文字列である「100republicaavemadrid」は、地図上にプロットされると、物理的距離がゼロであることが判る。したがって、NLD(61.9%)が80%の閾値を僅かに下回っていても、サニタイジングされたアドレスは、実際に同じPOIを表している。
図3を参照して説明すると、第1のサニタイジングされたアドレスは、地図300上に点305としてプロットされる。第2のサニタイジングされたアドレスは、300上に点310としてプロットされる。実際の関心点は、2本の街路320、325の交差点にあるホテル315である。第1及び第2の点305、310の間の距離330は、各点305、310の座標を判定することによって算出(又は推定)できる。一実施形態においては、地図300が座標を含む場合、座標を判定できる。点を地図300上に重ねたときに、座標を推定してもよい。
この場合も、距離330が実質的にゼロであるため、点305、310は、ホテル315に対応する同じPOIを表していると判定される。また、サーバ105は、ジオデータインスタンスの名称フィールド又は他のフィールドを比較することによって、第1及び第2の点の間の対応を確認してもよい。
図4は、本技術の例示的な方法のフローチャートである。この方法は、2つのマルチセグメント文字セット(例えば、ジオデータのインスタンス)を受信するステップ405を有する。2つのマルチセグメント文字セットのそれぞれは、複数のセグメント又はフィールドから構成されている。また、各フィールドは、フォーマットを有している。これらは、例えば、POI名、都市、番地、州、等である。
方法は、2つのマルチセグメント文字セットのそれぞれをサニタイジングするステップ410を含み、ここでは、まず、マルチセグメント文字列の複数のセグメントのうちの何れかのセグメントのフォーマットが標準化されたフォーマットでない場合、そのセグメントを標準化されたフォーマットに変換するステップ415を行う。この変換は、標準化されたフォーマットではないセグメント毎に実行してもよい。例えば、「fifth」、「5th」、「V」等のフィールドを、標準化されたフォーマットである「5」に変換してもよい。各フィールドは、必要に応じてサニタイジングしてもよい。
次に、サニタイゼーションは、変換されたセグメント及び変換されていないセグメントから連続する文字列を作成することによって2つのマルチセグメント文字セットのそれぞれを短縮するステップ420を含む。すなわち、幾つかのセグメント/フィールドは、サニタイジングしなくてもよい。サーバ105は、変換されたセグメント及び変換されていないセグメントの両方を1つの文字列に結合する。短縮処理は、大文字を小文字に変更するステップ425及び非英数字を除去するステップ430を含んでいてもよい。
次に、方法は、サニタイジングされたマルチセグメント文字セットを用いて距離スコアを算出するステップ435を含む。なお、距離スコアは、サニタイジングされたマルチセグメント文字セットの文字間の違いを表す。距離スコアを算出する方法については、図5を用いて以下に説明する。
図5は、正規化されたレーベンシュタイン距離(NLD)を算出する方法を例示的に示している。この方法は、第1及び第2のサニタイジングされた文字列(例えば、サニタイジングされた文字列)を受信するステップ505を含む。幾つかの実施形態においては、この方法は、第1及び第2の文字列の両方のレーベンシュタイン距離を算出するステップ510を含む。この方法は、更に第1及び第2の文字列のそれぞれの文字長を判定し、文字長を用いてNLDを算出するステップ515を含む。NLDは、上に詳しく説明した式1を用いて算出してもよい。
上述したように、NLDは、文字コンテンツに関して、文字列の「近さ」を表現するパーセンテージで表されるスコアである。例えば、「1234mainst」と「1234mainst」のNLDは、100%であり、「100avedereublicamadrid」と「100republicaavemadrid」のNLDは、61.9%である。
方法は、更に、NLDを閾値と比較するステップ520と、NLDが閾値に達していない又は閾値を超えていない場合に、第1及び第2の文字列の間の物理的距離計算を実行するステップ525とを含む。例えば、61.9%のNLDは、80%の閾値と比較される。NLDは、閾値に達していないので、サーバ105は、物理的距離計算を実行することができる。
例えば、サーバは、第1及び第2の文字列を地図上にプロットすることができ、具体的には、第1及び第2の文字列の番地をプロットすることができる。他の実施形態においては、第1及び第2の文字列が座標を含む場合、第1及び第2の文字列は、座標を用いてプロットしてもよい。プロットされた点の間の距離を判定し、距離閾値と比較してもよい。例えば、距離が100フィート未満である場合、プロットされた点は、同じPOIを表しているとみなすことができる。
図4及び図5のフローチャートは、フローチャートに示されているステップの幾つかを省略してもよいし、更にステップを追加してもよい。更に、フローチャートのステップは、本明細書に提供されている説明及び具体例に応じて、他のステップに置き換えることもできる。
図6は、ジオデータインスタンスのセグメント/フィールドの順列を作成及び使用し、ジオデータインスタンスの対についてのNLD値を算出し比較する方法のフローチャートである。上述したように、以下の例は、「マルチセグメント文字セット」としてのジオデータインスタンスを用いて説明される。
まず、2つのマルチセグメント文字セットのうちの第1のマルチセグメント文字セットを選択する。2つのマルチセグメント文字セットのうちの第2のマルチセグメント文字セットは、変更しなくてもよい。この方法は、2つのマルチセグメント文字セットのうちの第1のマルチセグメント文字セットを選択した後、2つのマルチセグメント文字セットのうちの第1のマルチセグメント文字セットから、複数の並べ替えられたマルチセグメント文字セットを作成するステップ605を有する。この処理は、2つのマルチセグメント文字セットのうちの1つのマルチセグメント文字セットの複数のセグメント内のセグメントの文字を再編成して、並べ替えられたセグメントを作成するステップを含む。再編成処理は、第1のマルチセグメント文字セットに対して、複数回実行され、複数の並べ替えられたマルチセグメント文字セットが生成される。
次に、この方法は、マルチセグメント文字セットの対を作成するステップを有する。これらの対は、マルチセグメント文字セットから並べ替えられた複数のマルチセグメント文字セットの1つと、第2のマルチセグメント文字セットとを含む。例えば、第1の対は、マルチセグメント文字セット「Hotel California, Los Angeles downtown」と第2のマルチセグメント文字セット「Los Angeles california hotel」を含む。第2の対では、並べ替えられたマルチセグメント文字セット「California Hotel Los Angeles downtown」が第2のマルチセグメント文字セット「Los Angeles california hotel」と対にされる。第3の対では、他の並べ替えられたマルチセグメント文字セット「Los Angeles California Hotel downtown」が第2のマルチセグメント文字セット「Los Angeles california hotel」と対にされる。
次に、この方法は、マルチセグメント文字セットの対をサニタイジングするステップ610を有する。上述のように、マルチセグメント文字セットの対は、複数の並べ替えられたマルチセグメントセットと、第2のマルチセグメント文字セットとの様々な組合せを含む。
ある実施形態においては、この方法は、マルチセグメント文字セットの対のそれぞれについて、正規化されたレーベンシュタイン距離(normalized Levenshtein distance:NLD)を算出するステップ615を有する。
幾つかの実施形態においては、この方法は、マルチセグメント文字セットの全ての対のうち、最高ランクのNLDを判定するステップを有する。
他の実施形態においては、この方法は、マルチセグメント文字セットの全ての対から最小のNLDを判定するステップ620を含む。NLDが最小の対は、ジオコーディングされたインスタンス(例えば、マルチセグメント文字セットの対)のうち最も一致する対であると考えられる。
図7は、コンピュータシステム1の形式の例示的なマシンのブロック図であり、このマシン内の一組の命令が実行されることによって、マシンは、本明細書に説明した動作の1つ以上を実行する。様々な例示的実施形態において、マシンは、独立型デバイスとして動作してもよく、他のマシンに接続(例えば、ネットワーク化)してもよい。ネットワーク化された構成では、このマシンは、サーバ−クライアントネットワーク環境におけるサーバ又はクライアントマシンの能力で動作してもよく、又はピアツーピア(又は分散型)ネットワーク環境のピアマシンとして動作してもよい。このマシンは、パーソナルコンピュータ(personal computer:PC)、タブレットPC、セットトップボックス(set-top box:STB)、個人携帯情報端末(personal digital assistant:PDA)、携帯電話機、携帯用音楽プレーヤ(例えば、携帯用ハードドライブ音声装置、例えば、MPEG(Moving Picture Experts Group)オーディオレイヤ3(MP3)プレーヤ)、ウェブ機器、ネットワークルータ、スイッチ又はブリッジ、又はマシンに実行させる動作を指定する一組の命令を(連続的又は他の形式で)実行することができる任意のマシンであってもよい。更に、1つのマシンのみを例示しているが、「マシン」という用語は、個別に又は連携して、一組(又は複数組)の命令を実行して、本明細書に説明した動作の1つ以上を実行するマシンのあらゆる集合体を含む。
例示的に示すコンピュータシステム1は、プロセッサ又は複数のプロセッサ5(例えば、中央演算処理装置(central processing unit:CPU)、グラフィックス処理装置(graphics processing unit:GPU)又はこれらの両方)と、それぞれバス20を介して互いに通信するメインメモリ10及びスタティックメモリ15とを含む。コンピュータシステム1は、更に、ビデオディスプレイ35(例えば、液晶ディスプレイ(liquid crystal display:LCD))を含んでいてもよい。コンピュータシステム1は、英数字入力デバイス30(例えば、キーボード)、カーソル制御装置(例えば、マウス)、音声認識又は生体認証ユニット(図示せず)、ドライブユニット37(ディスクドライブユニットとも呼ばれる)、信号生成デバイス40(例えば、スピーカ)、及びネットワークインターフェースデバイス45を含んでいてもよい。コンピュータシステム1は、更に、データを暗号化するデータ暗号化モジュール(図示せず)を含んでいてもよい。
ディスクドライブユニット37は、本明細書に説明した動作又は機能の何れか1つ以上を実現又は利用する命令(例えば、命令55)及びデータ構造の1つ以上の組が保存されるコンピュータ又はマシン可読媒体50を含む。命令55は、コンピュータシステム1による実行の間、メインメモリ10及び/又はプロセッサ5内に完全に又は部分的に常駐してもよい。また、メインメモリ10及びプロセッサ5もマシン可読媒体を構成してもよい。
更に、命令55は、幾つか周知の転送プロトコルの1つ(例えば、ハイパテキスト転送プロトコル(Hyper Text Transfer Protocol:HTTP))を利用するネットワークインターフェースデバイス45によって、ネットワーク140(図2参照)を介して送信又は受信してもよい。例示的な実施形態においては、マシン可読媒体50を1つの媒体として示しているが、「コンピュータ可読媒体」という用語は、一組以上の命令を保存する単一の媒体及び複数の媒体(例えば、集中型又は分散型データベース及び/又は関連するキャッシュ及びサーバ)を含む。また、「コンピュータ可読媒体」という用語は、マシンによって実行され、マシンがここに説明する方法の1つ以上を実現する一組の命令を保存し、符号化し、搬送することができるあらゆる媒体、又はこのような一組の命令に利用され若しくはこれに関係するデータ構造を保存し、符号化し、搬送することができるあらゆる媒体を含む。したがって、「コンピュータ可読媒体」という用語は、以下に限定されるわけではないが、ソリッドステートメモリ、光磁気媒体及び搬送波信号を含む。このような媒体は、以下に限定されるわけではないが、ハードディスク、フロッピー(登録商標)ディスク、フラッシュメモリカード、デジタルビデオディスク、ランダムアクセスメモリ(random access memory:RAM)、読出専用メモリ(read only memory:ROM)等を含む。本明細書に開示する例示的な実施形態は、コンピュータ上にインストールされたソフトウェア、ハードウェア、又はソフトウェア及びハードウェアの組合せによる動作環境で実現してもよい。
インターネットサービスは、インターネットサービスに接続された1つ以上の演算デバイスにインターネット接続を提供するように構成してもよく、演算デバイスは、1つ以上のプロセッサ、バス、メモリデバイス、表示デバイス、入出力デバイス等を含んでいてもよいことは、当業者の認識するところである。更に、インターネットサービスは、1つ以上のデータベース、レポジトリ、サーバ等に接続してもよく、これらを用いて、本明細書に開示した如何なる実施形態を実現してもよいことは、当業者の理解するところである。
特許請求の範囲における手段又はステップ・プラス・ファンクション・エレメント(step plus function elements)の全てに対応する構造、材料、動作及び均等物は、特定的に特許請求されている通り、他の特許請求された要素と連携してその機能を実行するためのあらゆる構造、材料及び動作を含むことを意図する。説明及び開示のために、本技術を記述したが、本明細書に開示した形式を本技術の全てであるとする意図、又は、本技術を本明細書に開示した形式に限定する意図はない。本技術の範囲及び精神を逸脱することなく、多くの修正及び変更が当業者にとって明らかである。本技術の原則及びその実用的なアプリケーションを最良に説明するために、及び当業者が本技術を理解し、特定の用途に適するように様々な修正を加えた様々な実施形態を想到できるように、例示的な実施形態を選択し、記述した。
以上では、本技術の実施形態に基づく方法、装置(システム)及びコンピュータプログラム製品のフローチャート実現例及び/又はブロック図を参照して、本技術の側面を記述した。フローチャート実現例及び/又はブロック図の各ブロック、又はフローチャート実現例及び/又はブロック図のブロックの組合せは、コンピュータプログラム命令によって実現してもよいことは明らかである。これらのコンピュータプログラム命令は、汎用コンピュータ、専用コンピュータ又はマシンを構成する他のプログラム可能なデータ処理装置のプロセッサに供給してもよく、命令は、コンピュータ又は他のプログラム可能なデータ処理装置のプロセッサによって実行されて、フローチャート及び/又はブロック図の1つ又は複数のブロックによって特定されている機能/動作を実現するための手段を構成する。
これらのコンピュータプログラム命令は、コンピュータ、他のプログラム可能なデータ処理装置又は他のデバイスに特定の方式で機能するように指示を与えるコンピュータ可読媒体に保存してもよく、これによって、コンピュータ可読媒体に保存された命令は、フローチャート及び/又はブロック図の1つ又は複数のブロックで特定されている機能/動作を実現する命令を含む製品を構成する。
コンピュータプログラム命令は、コンピュータ、他のプログラム可能なデータ処理装置又は他のデバイスにロードしてもよく、これによって、コンピュータ、他のプログラム可能な装置又は他のデバイスに、コンピュータによって実現される処理を実行させる一連の動作ステップを実行させ、コンピュータ又は他のプログラム可能な装置上で実行される命令は、フローチャート及び/又はブロックの1つ又は複数のブロックで指定されている機能/動作を実現する処理を提供する。
図に示すフローチャート及びブロック図は、本技術の様々な実施形態に基づくシステム、方法及びコンピュータプログラム製品の可能な具体例のアーキテクチャ、機能及び動作を例示する。これに関して、フローチャート又はブロック図内の各ブロックは、特定の論理機能を実現するための1つ以上の実行可能な命令を含むモジュール、セグメント又はコードの一部を表していてもよい。なお、幾つかの変形例では、ブロックに示した機能は、図に示す順序とは異なる順序で実行してもよい。例えば、連続して示される2つのブロックは、関係する機能に応じて、実際には、実質的に並行して実行してもよく、逆の順序で実行してもよい。また、例示したブロック図及び/又はフローチャートにおける各ブロック及び/又はフローチャートの複数のブロックの組合せは、特定の機能又は動作を実行する特定用途のハードウェアベースのシステムによって実現してもよく、特定用途のハードウェア及びコンピュータ命令の組合せによって実現してもよい。
以上では、例示を目的としてシステムの特定の実施形態及びこの具体例を記述したが、当業者が理解するように、システムの範囲内で、様々な等価な変更が可能である。例えば、処理又はステップを所与の順序で示したが、他の実施形態では、異なる順序のステップを有するルーチンを実行してもよく、幾つかの処理又はステップを削除し、移動し、追加し、再分割し、組合せ及び/又は変更して、代替又は下位の組合せを提供してもよい。これらの処理又はステップのそれぞれは、様々な異なる手法で実行してもよい。また、処理又はステップは、同じ時刻に順番に実行されるように示しているが、これらの処理又はステップは、並列的に実行してもよく、異なる時刻に実行してもよい。
様々な実施形態を記述してきたが、これらは、例示的なものに過ぎず、限定的なものではない。この説明は、本発明の範囲を本明細書に述べる特定の形式に制限することを目的としない。これとは反対に、この記述は、特許請求の範囲に定義され、或いは当業者にとって理解される本発明の思想及び範囲内に含まれるように、代替例、変形例及び等価物を包含することを意図する。このように、好ましい実施形態の幅及び範囲は、上述した例示的な実施形態の何によっても制限されない。



  1. プロセッサと、実行可能な命令を保存するメモリとを備えるコンピュータによって実行される方法であって、前記プロセッサが前記命令を実行することによって実現される方法において、
    それぞれがフォーマットを有する複数のセグメントをそれぞれ有する2つのマルチセグメント文字セットを受信するステップと、
    前記セグメントのフォーマットが標準化されたフォーマットでない場合、前記マルチセグメント文字セットの複数のセグメント内のセグメントを標準化されたフォーマットに変換し、前記変換されたセグメント及び変換されていないセグメントから連続する文字列を作成して、前記2つのマルチセグメント文字セットのそれぞれを短縮することにより、前記2つのマルチセグメント文字セットをサニタイジングするステップと、
    サニタイジングされた前記マルチセグメント文字セットを用いて、サニタイジングされた前記マルチセグメント文字セットの文字間の差を表す距離スコアを算出するステップと
    を有する方法。

  2. 前記サニタイジングするステップは、更に、前記複数のセグメントから非英数字を削除するステップを含む請求項1記載の方法。

  3. 前記サニタイジングするステップは、更に、前記複数のセグメントのそれぞれの大文字を小文字に変換するステップを含む請求項1記載の方法。

  4. 前記複数のセグメントの少なくとも1つは、第1の言語で表され、前記複数のセグメントの少なくとも1つは、第2の言語で表されている請求項1記載の方法。

  5. 前記距離スコアを算出するステップは、サニタイジングされた前記マルチセグメント文字セットについてのレーベンシュタイン距離(LDexp1)を算出するステップを含む請求項1記載の方法。

  6. 前記距離スコアを算出するステップは、サニタイジングされた前記マルチセグメント文字セットについての正規化されたレーベンシュタイン距離(NLD)を算出するステップを含み、前記正規化されたレーベンシュタイン距離は、以下の式を用いて算出される、請求項5記載の方法。
    NLD=1−(LDexp1−abs([LSexp1]−[LSexp2]))/min([LDexp1],[LSexp2])
    ここで、LSexp1は、サニタイジングされた前記マルチセグメント文字セットの第1の文字列の長さであり、LSexp2は、サニタイジングされた前記マルチセグメント文字セットの第2の文字列の長さであり、LDexp1は、サニタイジングされた前記マルチセグメント文字セットのLDである。

  7. 前記NLDをパーセンテージスコアに変換するステップを更に有する請求項6記載の方法。

  8. 前記2つのマルチセグメント文字セットのうちの第1のマルチセグメント文字セットの複数のセグメント内のセグメントの文字を再編成して、並べ替えられたセグメントを生成することにより、前記2つのマルチセグメント文字セットのうちの前記第1のマルチセグメント文字セットから、複数の、並べ替えられたマルチセグメント文字セットを作成するステップと、
    前記複数の並べ替えられたマルチセグメント文字セットと、前記2つのマルチセグメント文字セットのうちの第2のマルチセグメント文字セットとの様々な組合せを含むマルチセグメント文字セットの対をサニタイジングするステップと、
    前記マルチセグメント文字セットの対のそれぞれについて正規化されたレーベンシュタイン距離(NLD)を算出するステップとを更に有する請求項1記載の方法。

  9. 実行可能な命令を保存するメモリと、
    前記実行可能な命令を実行して、
    それぞれがフォーマットを有する複数のセグメントをそれぞれ有する2つのマルチセグメント文字セットを受信し、
    セグメントのフォーマットが標準化されたフォーマットでない場合、前記マルチセグメント文字セットの前記複数のセグメント内のセグメントを標準化されたフォーマットに変換し、変換された前記複数のセグメントから連続する文字列を作成して、前記2つのマルチセグメント文字セットのそれぞれを短縮することにより、前記2つのマルチセグメント文字セットをサニタイジングし、
    サニタイジングされた前記マルチセグメント文字セットについて正規化されたレーベンシュタイン距離(NLD)を算出するプロセッサと
    を備え、
    前記正規化されたレーベンシュタイン距離は、
    サニタイジングされた前記マルチセグメント文字セットについてのレーベンシュタイン距離(LDexp1)を算出し、
    以下の式を用いて前記LDexp1を正規化することによって算出される、演算デバイス。
    NLD=1−(LDexp1−abs([LSexp1]−[LSexp2]))/min([LDexp1],[LSexp2])
    ここで、LSexp1は、サニタイジングされた前記マルチセグメント文字セットの第1の文字列の長さであり、LSexp2は、サニタイジングされた前記マルチセグメント文字セットの第2の文字列の長さであり、LDexp1は、サニタイジングされた前記マルチセグメント文字セットのLDである。

  10. 前記プロセッサは、更に、前記複数のセグメントのそれぞれから非英数字を削除することにより、サニタイジングの命令を実行する請求項9記載の演算デバイス。

  11. 前記プロセッサは、更に、前記複数のセグメントのそれぞれの大文字を小文字に変換することにより、サニタイジングの命令を実行する請求項9記載の演算デバイス。

  12. 更に、前記NLDをパーセンテージスコアに変換するステップを有する請求項9記載の演算デバイス。

  13. 前記2つのマルチセグメント文字セットのそれぞれは、地図上の関心点を表す請求項9記載の演算デバイス。

  14. 前記2つのマルチセグメント文字セットのそれぞれを関心点として地図上にプロットし、
    前記プロットの間の物理的距離を算出し、
    前記物理的距離が距離閾値を下回る場合、前記2つのマルチセグメント文字セットが同じ関心点を表すと特定するステップを更に有する請求項9記載の演算デバイス。

  15. プロセッサと、実行可能な命令を保存するメモリとを備える演算デバイスによって実行されるジオコーディング方法であって、前記プロセッサが前記命令を実行することによって実現される方法において、
    それぞれがフォーマットを有する複数のセグメントをそれぞれ有し、同じ関心点を表現する可能性がある2つのジオデータ文字列を受信するステップと、
    セグメントのフォーマットが標準化されたフォーマットでない場合、前記ジオデータ文字列の複数のセグメント内のセグメントを標準化されたフォーマットに変換するステップと、
    変換された複数の前記セグメントから連続する文字列を作成することによって、前記2つのジオデータ文字列のそれぞれを短縮するステップと、
    サニタイジングされたマルチセグメント文字セットを用いて、短縮されてサニタイジングされた前記2つのジオデータセグメント文字列の文字の差を表す距離スコアを算出するステップと、
    前記距離スコアを閾値と比較するステップと、
    前記距離スコアが閾値を下回る場合、データベースにおいて、前記2つの短縮され、サニタイジングされたジオデータ文字列が、同じ関心点を表していると特定するステップとを有する方法。

  16. 前記複数のセグメントは、POI名、都市、番地、州、国、郵便番号、電話番号、ファックス番号、ウェブサイトURL、座標及びこれらの組合せのいずれかを含む請求項15記載の方法。

  17. 前記ジオデータ文字列のそれぞれを関心点として地図上にプロットするステップと、
    前記プロットの間の地理的距離を算出するステップと、
    前記地理的距離が距離閾値を下回る場合、前記2つのジオデータ文字列が同じ関心点を表していると特定するステップとを更に有する請求項15記載の方法。

  18. サニタイジングするステップは、更に、前記複数のセグメントから非英数字を削除するステップを含む請求項15記載の方法。

  19. サニタイジングするステップは、更に、前記複数のセグメントのそれぞれの大文字を小文字に変換するステップを含む請求項15記載の方法。

  20. 前記複数のセグメントの少なくとも1つは、第1の言語で表され、前記複数のセグメントの少なくとも1つは、第2の言語で表されている請求項15記載の方法。

  21. 関心点を地図上にプロットするステップを更に有し、前記関心点は、サニタイジングされた前記ジオデータセグメント文字列が同じ関心点を表すと判定される場合、サニタイジングされた前記ジオデータセグメント文字列によって定義される請求項15記載の方法。

 

 

Patent trol of patentswamp
類似の特許
非常に小さな粒子径を有するマイクロカプセル内に熱変色性系顔料を製造する方法。現在開示されている手段は、上で概説した課題を克服し、また、非常に小さな粒子サイズを有するカプセルに内包したスラリーの大バッチの製造プロセスを提供することにより、技術を前進させるものである。例えば、上記のより小さなカプセルは種々の方法により記載することができる。顔料は、ガウス分布した粒子径を有し、主に、約400nmから1.5ミクロンのプラスマイナス10%の範囲内である。
1またはそれより多くの触媒有機金属酸化物材料(例えば、金属セッケン)を含む安定化剤を添加することにより、マイクロカプセル化プロセスが改善される。これは、マイクロカプセルの壁中の不飽和結合を反応させて、コーティングへの添加物(これは、他の場合には、マイクロカプセルのコアのサーモクロミックまたはフォトクロミック材料の官能基を分解する)の影響に対してマイクロカプセルを安定化することによって架橋剤として機能する。
【課題】実世界の場所を表示するコンピュータゲームを作成する方法を提供する。
【解決手段】コンピュータゲームは、ゲームのプレイ筋書きの一部分として実際の又は想像上の地理的現場を描写又は表示する。コンピュータゲームは、現場における道路のような地理的特徴を表わすデータを含む地図データベースを使用する。ゲームエンジンプログラムは、ゲームのユーザインターフェイスを介してユーザにゲームプレイ筋書きをプレゼンテーションする。アプリケーションプログラミングインターフェイスプログラムは、ゲームエンジンプログラムからのデータの要求を受け容れ、地図データベースからのデータにアクセスし、そしてそのデータを適当なフォーマットでゲームエンジンプログラムに供給し、ユーザにゲーム筋書きをプレゼンテーションするのに使用する。
【選択図】図2
【課題】本発明は、顔料分散体、特に、粘度などの改善された性能特性を有し、それによって、従来の改質顔料に対する有利な代替案を提供する高含有顔料を有する。
【解決手段】本発明は、粒子状物質および溶媒を任意の分散剤と共に含む分散体に関する。溶媒は低誘電率を有し、粒子状物質は高含有レベルで存在する。得られる分散体は、高粒子状物質含有においてさえも安定であり、低粘度を有することが見出されてきた。これらの分散体に対する種々の用途もまた開発されている。
【選択図】なし
【課題】複数のクライアント・デバイスにおいて地図の画像を集めて、その画像を地球に関して配向し、この配向された地図をユーザーに提供すること。
【解決手段】地図画像415は、地球画像510の絵の上に画像の位置を配置することにより地図を配向させるユーザーによって集められ得る。他の例においては、ユーザーは、地球の画像上の二つ以上の位置に対して地図画像415における二つ以上の点の位置を示す「プッシュピン」を用いて地図を配向し得る。この画像は、次いでダウンロードされて、他のユーザーによって使用し得る高画質画像を生成する目的で処理し得る。
【選択図】図5
【課題】均質な固溶比である固溶体顔料ナノ粒子を提供することを課題とする。
【解決手段】少なくとも2種類の顔料が溶媒に溶解された少なくとも1種類の顔料溶液、または少なくとも1種類の顔料が溶媒に溶解された少なくとも2種類の顔料溶液と顔料析出用溶媒とを混合して少なくとも2種類の顔料を析出させて作製される固溶体顔料ナノ粒子であり、上記顔料析出用溶媒と混合された上記顔料溶液における少なくとも2種類の顔料の比に対する、析出させた固溶体顔料ナノ粒子の一次粒子中における少なくとも2種類の顔料の固溶比が精度25%以内である事を特徴とする固溶体顔料ナノ粒子を提供する。
【選択図】図5
【課題】本発明は、地図及び指令をプリントするためのシステム、方法、及びコンピュータ読み取り可能な媒体に関する。【解決手段】指令をプリントするインストラクションを受け取るのに応答して、装置は、移動すべきルートを、そのルートに対応する個別のステップと共に示すのに最適なレイアウトを定義する。そのレイアウトは、ルート全体を示す概略地図を、ルート上の各ステップを識別する吹き出しと共に含む。又、レイアウトは、個々のステップのリストも含み、各リストは、吹き出しを参照する参照番号及びステップの記述を含む。又、各リストは、リストに対応するステップの詳細図を示す地図タイルも含む。概略地図及びリストは、例えば、風景画的な図の異なる列に配置される。【選択図】図5
【課題】インクジェット用の新しいインク組成のための改質顔料、及び該改質顔料の調整方法を提供する。
【手段】顔料と、化学式HN−A−Yを有する少なくとも1種類の試薬(YはH、C1−C12アルキル基、芳香族基、ポリマー基、又は−c(0)-A-NH官能基であり、AはO、HN、又はS)との反応生成物を改質顔料とする。
【選択図】図1
ユーザーが入力した電子地図の起動指令を受信すると、電子地図のフィルタ情報を取得するステップ(11)と、所定の複数の電子地図から、前記電子地図のフィルタ情報とマッチングする電子地図を確定するステップ(12)と、を備える電子地図の確定方法及び装置を提供する。これにより、ユーザーが必要とするときに要求された通りにカレントの電子地図のフィルタ情報と最もマッチングする電子地図をフレキシブルに選択することができ、シンプルな電子地図を使用せず、従来技術で提供された電子地図が比較的にシンプルで、フレキシビリティが悪いという問題を避けられる。
【選択図】図1
波長変換ポリマー膜 // JP2015537088
本発明は、無機蛍光化合物および有機蛍光化合物を含むポリマー膜に関する。本発明はさらに、かかる膜の製造方法、および太陽電池における波長変換膜としてのその使用に関する。
To top