(57)【要約】  電子デバイスにおいて受け付けられた文字の入力ストリングに基づいて１又は複数の複数語候補を提案するためのコンピュータ実装方法、デバイス、及びシステムが提供される。当該方法は、ａ）受け付けられた入力ストリングのｎ個の選択された部分の各々について、ｑ語の固定辞書からｍ個の単語の候補を選択する段階であって、ｎ、ｍ、及びｑはそれぞれ正の整数を含み、ｎは２より大きいか又はそれに等しく、ｍはｑより小さい、段階と、ｂ）結果として得られたｍｎ個の単語の候補の組み合わせから、単語の組み合わせの候補のサブセットｐを選択する段階であって、ｐは正の整数であり、ｐはｍｎより小さい、段階とを含む。いくつかの実施形態では、複数語候補は、各一意の地理的位置に解決され得、複数語候補、又はそれらの解決された地理的位置のサブセットは、ユーザが選択するために電子デバイスにおいて提示され得る。受け付けられた入力ストリングのｎ個の選択された部分は、ｎ＝ｘであるような受け付けられた単語入力ストリングを含むｘ個の単語を含むことが好ましい。
2018506114.tif 000002
【特許請求の範囲】
【請求項１】
電子デバイスにおいて受け付けられた入力ストリングに基づいて、１又は複数の複数語候補を提案するためのコンピュータ実装方法であって、
ａ）受け付けられた入力ストリングのｎ個の選択された部分の各々について、ｑ語の固定辞書からｍ個の単語の候補を選択する段階であって、ｍ、ｎ、及びｑは正の整数を含み、ｎは２より大きいか又はそれに等しく、ｍはｑより小さい、段階と、
ｂ）結果として得られたｍｎ個の単語の候補の組み合わせから、単語の組み合わせの候補のサブセットｐを選択する段階であって、ｐは、正の整数であり、ｐは、ｍｎより小さい、段階と
を備える方法。
【請求項２】
前記受け付けられた入力ストリングの前記ｎ個の選択された部分は、ｎ＝ｘであるような前記受け付けられた単語入力ストリングを含むｘ個の単語を含む、請求項１に記載の方法。
【請求項３】
段階ａ）は、前記受け付けられた入力ストリングの前記ｎ個の選択された部分の各々について、前記固定辞書の前記ｑ語の一部又は全部の各スコア又はランキングを決定又は割り当てて、それにより、最高のスコア又はランキングに基づいて、前記受け付けられた入力ストリングの前記ｎ個の選択された部分の各々について、ｑ語の前記固定辞書から前記ｍ個の単語の候補を選択する段階を含む、請求項１又は２に記載の方法。
【請求項４】
前記受け付けられた入力ストリングの前記ｎ個の選択された部分の各々についての前記固定辞書の前記ｑ語の一部又は全部の前記スコア又はランキングは、前記受け付けられた入力ストリングの前記ｎ個の選択された部分の各々の文字ストリングと、前記固定辞書の前記ｑ語の一部又は全部の前記文字ストリングとの間の比較に基づく文字ベースの距離スコアを含む、請求項３に記載の方法。
【請求項５】
前記文字ベースの距離スコアは、編集距離スコア、重み付き編集距離スコア、レーベンシュタイン編集距離スコア、重み付きレーベンシュタイン編集距離スコア、転置を考慮する編集距離スコア、転置を考慮する重み付き編集距離スコア、転置を考慮するレーベンシュタイン編集距離スコア、又は、転置を考慮する重み付きレーベンシュタイン編集距離スコアを含む、請求項４に記載の方法。
【請求項６】
段階ｂ）は、前記単語の組み合わせの候補の一部又は全部の各スコア又はランキングを決定又は割り当て、それにより、最高のスコア又はランキングに基づいて、単語の組み合わせの候補の前記サブセットｐを選択する段階を含む、請求項１から５の何れか一項に記載の方法。
【請求項７】
段階ｂ）は、二分ヒープにおいて任意選択で実装された優先度付きキューデータ構造を使用することによって、単語の組み合わせの候補の前記サブセットｐを選択する段階を含む、請求項６に記載の方法。
【請求項８】
前記固定辞書は、単語の順序付けられたリストを含む、請求項１から７の何れか一項に記載の方法。
【請求項９】
前記単語の組み合わせの候補はそれぞれ、一意の側面に解決され得、前記方法は更に、前記単語の組み合わせの候補の一部又は全部をそれらの一意の側面に解決する段階と、前記電子デバイスにおいて提示するために、前記一意に解決された側面のサブセットを選択する段階とを備える、請求項１から８の何れか一項に記載の方法。
【請求項１０】
単語の組み合わせの候補の前記解決された側面は、一意の地理的位置を含む、請求項９に記載の方法。
【請求項１１】
各解決された地理的位置のランキング又はスコアは、各解決された地理的位置の、前記電子デバイスの現在の又は最新の既知の位置までの距離、及び、各解決された地理的位置の、最も近い予め定められた地図に基づいた地物までの距離のうち少なくとも１つの決定を含む、請求項１０に記載の方法。
【請求項１２】
前記方法は、前記電子デバイスにおいて完全に実装される、請求項１から１１の何れか一項に記載の方法。
【請求項１３】
前記方法は、サーバベースの方法である、請求項１から１１の何れか一項に記載の方法。
【請求項１４】
受け付けられた入力ストリングに基づいて１又は複数の複数語候補を提案するための携帯型電子デバイスであって、
機械可読命令を格納するメモリと、
前記機械可読命令を実行して請求項１から１３の何れか一項に記載の方法の段階を実施するプロセッサとを備える携帯型電子デバイス。
【請求項１５】
受け付けられた入力ストリングに基づいて１又は複数の複数語候補を提案するためのシステムであって、
機械可読命令を格納するメモリと、前記機械可読命令を実行するプロセッサとを有するサーバと、
機械可読命令を格納するメモリと、前記機械可読命令を実行するプロセッサとを有する携帯型電子デバイスとを備え、
前記サーバ及び前記携帯型電子デバイスは、ネットワークを通じて互いに通信し、
前記携帯型電子デバイスにおける受け付けられたストリングに基づいて前記携帯型電子デバイスによって前記サーバに送信された要求に応答して、前記サーバは、請求項１から１１の何れか一項に記載の方法の段階を実施する、
システム。
【請求項１６】
請求項１から１３の何れか一項に記載の方法の段階を携帯型電子デバイスのプロセッサに実施させるためのプログラム。
【請求項１７】
請求項１から１１の何れか一項に記載の方法の段階をサーバのプロセッサに実施させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子デバイスにおいて受け付けられた入力ストリングに基づいて、より具体的には、電子デバイスにおいて受け付けられた複数語入力ストリングに基づいて、１又は複数の複数語候補を提案するためのコンピュータ実装方法に関する。
【背景技術】
【０００２】
位置を特定すべく、緯度及び経度の座標、又はグリッド参照などの幾何学的数値座標を使用することはよく知られており、衛星利用位置特定システムは通常、そのような数値座標を使用して位置を特定する。位置を特定すべく数値座標を使用することの実際的な問題の１つは、結果として生じる数字ストリングが非常にユーザにとって不親切なものであるということである。実際には、人々は通常、数字ストリングは、正確に覚えること、又は他人に言葉で伝えることが困難であると感じている。場合によって、位置は、郵便番号又は通りの名前などの他の手段を、おそらく建物番号と併せて使用して特定されるが、これらの手法は、それらが比較的不正確なことがあり、通常建物だけにしか割り当てられないという問題に悩まされる。特に、郵便番号は通常、郵便物が配達される、又は受け取られることが期待される場所にだけ割り当てられる。その結果、これらの手法は、適切なコード、名前、及び番号が高密度に割り当てられた都市部でしか役立たないことが多い。
【０００３】
出願人の、２０１４年４月１４日に出願された国際（ＰＣＴ）特許出願番号ＰＣＴ／ＧＢ２０１４／０５１１５２（出願人が先に開示したシステム）は、位置識別子を生成する方法を開示している。当該方法は、位置の地理座標を取得する段階と、地理座標を一意の単語群に変換する段階とを備える。複数の単語は、覚えやすい位置識別子として提供される。逆に、位置の地理座標を、その関連付けられた一意の単語群から特定することが可能である。
【０００４】
出願人が先に開示したシステムにおいて、携帯型電子デバイスのユーザ、例えば、スマートフォンのユーザは、彼らのスマートフォンにおいて、彼らの現在位置又は選択された位置の特定を要求してよい。それに応答して、スマートフォンは、現在位置の座標を取得する。座標は通常、例えば、"５２．１２３４５６、−０．６５４３２１"といった、緯度及び経度の座標として小数点以下６桁まで提供される。位置座標は、一般に'ＧＰＳ'と呼ばれるシステムなどのほとんどの衛星利用ナビゲーションシステムからこの精度で容易に得られる。取得された位置の緯度及び経度の座標は、例えば、文字ストリング内においてピリオドで区切られてよい"ｔａｂｌｅｔ．ｍｉｃｒｏｐｈｏｎｅ．ｅｘｃｉｔｅｄ"といった一意の３語連鎖を含む位置識別子に解決されるが、このことは必須ではない。この変換は、出願人の先の開示において説明されているように、適切な可逆アルゴリズムを使用して実行される。 
【０００５】
ユーザは、単語連鎖位置を、ユーザの交流相手と単語連鎖位置を共有することを含む多数のやり方で使用してよい。プロセスは完全に可逆なので、ユーザの交流相手は、彼ら自身のハンドヘルドデバイスを使用して単語ベースの位置識別子を解決し、送信者が選択した位置に関連する位置座標を受け付け、これを彼らのスマートフォン（又は、他の適切なデバイス）におけるマップビュー上に表示できる。
【０００６】
しかしながら、ユーザは、単語ベースの位置識別子を、特に、これが受け付け後しばらくして入力される場合、ミスタイプし、及び／又は間違って記憶するかもしれず、それにより、解決不可能な単語ベースの位置識別子の入力、すなわち、容認できる入力として認識されない単語ベースの位置識別子の結果として、彼らはおそらく、誤った地理的位置の解決を受ける、又は、位置出力を全く受けないということになるという点で問題が生じることがある。この問題は、例えば、どの国に、又は適用可能ならば、どの都市に解決された地理的位置があるのか、又は近いのかを強調し、これにより、ユーザが、それが正しい又は期待される出力であるかどうかを判断でき、それにより、エラーが起こったかもしれないことをユーザに明らかにすることによって、ある程度までユーザインタフェース内で緩和され得る。 
【０００７】
エラーを特定し、位置の正しい３語連鎖を復元する上では、かなりの技術的困難がある。これら困難は、限定はされないが、以下のものを含む。
（ｉ）必要な応答時間は、ユーザに効果的であるよう短くなくてはならないが、出願人が先に開示したシステムでは、ユーザが意図したかもしれない、考えられる３語の組み合わせが約５７兆個あり、最新のデスクトップパーソナルコンピュータにおいてですら、これらを一つずつスキャンするプロシージャはどれも実現可能でなく、ハンドヘルド又は携帯型の電子デバイスにおいてはなお一層実現可能ではない。
（ｉｉ）１つの選択肢を検討する場合、受け付けられた元の入力文字ストリング又はそのようなストリングの一部に対するその近接度をある程度のものにする必要がある。このプロシージャは、何度も、すなわち、ユーザが意図したかもしれない位置の各々について一回呼び出されるので、この場合も計算効率のよいことを必要とする。
（ｉｉｉ）当該方法は、メモリが限られていることが多いスマートフォン又はタブレットコンピュータ又は同様のものなどの携帯型又はハンドヘルドの電子デバイスにおいて動作するよう適合される必要があり、したがって、当該方法は、できるだけ少ないメモリを利用する必要がある。 
【０００８】
［本発明の目的］
本発明の目的は、入力文字ストリングの予想される置き換えとして、単語の候補又は単語の組み合わせの候補を選択又は提案するためのシステムに関連する１又は複数の問題をある程度まで緩和又は除去することである。
【０００９】
上記の目的は、主クレームの特徴の組み合わせによって達成される。従属クレームは本発明の更に有益な実施形態を開示する。
【００１０】
本発明の別の目的は、出願人が先に開示したシステムに関連する１又は複数の問題をある程度まで緩和又は除去することである。
【００１１】
本発明の別の目的は、既知の地理的位置解決システムに関連する１又は複数の問題をある程度まで緩和又は除去することである。
【００１２】
本発明の別の目的は、処理が必要な位置の数をヒューリスティックに低減する１又は複数の方法を提供することである。ここで、そのような位置は、ユーザが期待している結果であるかもしれない。
【００１３】
当業者ならば、以下の説明から、本発明の他の目的を導き出すであろう。従って、上記の目的の記述は、網羅的ではなく、単に本発明の多数の目的の一部を示す役割を果たす。
【発明の概要】
【００１４】
第１の主態様において、本発明は、電子デバイスにおいて受け付けられた入力ストリングに基づいて、１又は複数の複数語候補を提案するためのコンピュータ実装方法を提供する。当該方法は、ａ）受け付けられた入力ストリングのｎ個の選択された部分の各々について、ｑ語の固定辞書からｍ個の単語の候補を選択する段階であって、ｍ、ｎ、及びｑは正の整数を含み、ｎは２より大きいか又はそれに等しく、ｍはｑより小さい、段階と、ｂ）結果として得られたｍｎ個の単語の候補の組み合わせから、単語の組み合わせの候補のサブセットｐを選択する段階であって、ｐは正の整数であり、ｐはｍｎより小さい、段階とを備える。受け付けられた入力ストリングのｎ個の選択された部分は、ｎ＝ｘであるような当該受け付けられた単語入力ストリングを含むｘ個の単語を含むのが好ましい。
【００１５】
第２の主態様において、本発明は、受け付けられた入力ストリングに基づいて、１又は複数の複数語候補を提案するための携帯型電子デバイスを提供する。当該デバイスは、機械可読命令を格納するメモリ、及び、本発明の第１の主態様に係る方法の段階を実施すべく当該機械可読命令を実行するよう構成されたプロセッサを備える。
【００１６】
第３の主態様において、本発明は、受け付けられた入力ストリングに基づいて、１又は複数の複数語候補を提案するためのシステムを提供する。当該システムは、機械可読命令を格納するメモリ、及び、当該機械可読命令を実行するよう構成されたプロセッサを有するサーバと、機械可読命令を格納するメモリ、及び当該機械可読命令を実行するよう構成されたプロセッサを有する携帯型電子デバイスとを備え、当該サーバ及び当該携帯型電子デバイスは、ネットワークを通じて互いに通信するよう構成されており、携帯型電子デバイスにおいて、受け付けられたストリングに基づいて当該デバイスによってサーバに送信された要求に応答して、サーバは、本発明の第１の主態様に係る方法の段階を実施する。 
【００１７】
第４の主態様において、本発明は、本発明の第１の主態様に係る方法の段階を実施するための、携帯型電子デバイスのプロセッサによって実行可能な機械可読命令を格納するコンピュータ可読媒体を提供する。
【００１８】
第５の主態様において、本発明は、本発明の第１の主態様に係る方法の段階を実施するための、サーバのプロセッサによって実行可能な機械可読命令を格納するコンピュータ可読媒体を提供する。
【００１９】
本発明の概要は、必ずしも、本発明を定義するために必須の全ての特徴を開示しているわけではなく、本発明は、開示されている特徴の部分的組み合わせに在してよい。
【図面の簡単な説明】
【００２０】
本発明の上記の特徴及び更なる特徴が、次の添付の図面に関連してほんの一例として提供されている以下の好適な実施形態の説明から明らかになる。
【図１】本発明に係るシステムの例を示す図である。
【図２】図１のシステムにおいて使用されるユーザデバイスの例を示す図である。
【発明を実施するための形態】
【００２１】
以下の説明は、好適な実施形態をほんの一例として、かつ、本発明を実行に移すために必要な特徴の組み合わせに限定することなく説明するものである。
【００２２】
本明細書における「一実施形態」又は「実施形態」に関する言及は、当該実施形態に関連して説明される特定の特徴、構造、又は特性が、本発明の少なくとも１つの実施形態に含まれることを意味している。本明細書の様々な箇所における「一実施形態において」という文言の出現は、必ずしも全てが同じ実施形態を指すわけではなく、他の実施形態を互いに排除する別個の又は代替の実施形態であるわけでもない。更に、いくつかの実施形態によって示され得、他の実施形態によっては示され得ない様々な特徴が説明される。同様に、いくつかの実施形態の要件であり得、他の実施形態の要件ではあり得ない様々な要件が説明される。
【００２３】
図に示される要素は、様々な形態のハードウェア、ソフトウェア、又はそれらの組み合わせで実装されてよいことを理解されたい。これらの要素は、プロセッサ、メモリ、及び入出力インタフェースを含んでよい１又は複数の適切にプログラムされた汎用デバイスにおいて、ハードウェアとソフトウェアとの組み合わせで実装されるのが好ましい。 
【００２４】
本説明は、本発明の原理を示している。したがって、当業者ならば、本発明の原理を具現化し、その主旨及び範囲内に含まれる様々な構成を、本明細書においては明示的に説明も示されもしていないが、案出できることが理解される。 
【００２５】
更に、本明細書において本発明の原理、態様、及び実施形態、並びにそれらの特定の例を記載する全ての記述は、それらの構造的等価物及び機能的等価物の両方を包含するよう意図されている。加えて、そのような等価物は、現在知られている等価物、及び将来開発される等価物、すなわち、構造を問わず、同一の機能を実行する開発されるあらゆる要素、の両方を含むことが意図されている。
【００２６】
本明細書の特許請求の範囲において、特定の機能を実行するための手段として表わされる任意の要素は、その機能を実行する何れかのやり方を包含するよう意図されている。そのやり方は、例えば、ａ）その機能を実行する回路素子の組み合わせ、又は、ｂ）任意の形態のソフトウェアであって、従って、ファームウェア、マイクロコード又は同様のものを含み、当該ソフトウェアを実行してその機能を実行するための適切な回路と組み合わせられた、任意の形態のソフトウェアを含む。そのような特許請求の範囲によって定義される本発明は、記載した様々な手段によって提供された機能が、特許請求の範囲が必要とする態様で組み合わせられ、まとめられるという事実に在する。したがって、それらの機能を提供できるあらゆる手段は、本明細書において示されるものと等価であると見なされる。 
【００２７】
図を参照すると、本発明のシステム１は、いくつかのユーザデバイス２及びセントラルサーバ３を備える。ユーザデバイス２は、スマートフォン、タブレットコンピュータ、又は同様のものなどのハンドヘルド及び／又は携帯型の電子デバイス２ａ、及び／又はパーソナルコンピュータ（ＰＣ）２ｂを含む。ユーザデバイス２の各々は、インターネット４などのネットワークを通じてセントラルサーバ３と通信可能であるが、このことは、本発明の方法が電子デバイス２ａ又はＰＣ２ｂにおいて完全に実行される場合には必須ではない。そのような場合では、電子デバイスは、ネットワークに接続される必要はない。明確にするために、図１では３つだけの電子デバイス２ａと、１つのＰＣ２ｂとが示されているが、実際には、システム１は多数の電子デバイス２を含んでよいことが理解されるであろう。しかし、本発明の方法が１つの電子処理デバイス２において実装されてよいときは、このこともまた必須ではない。
【００２８】
図２は、システム１の電子デバイス２ａの例を更に詳細に示している。図２に示されるように、電子デバイス２ａは、データプロセッサ１０、視覚ディスプレイ１１、ユーザ命令がデバイス２ａに入力され、情報がユーザに提示及び／又は表示されることを可能にするユーザインタフェース１２、スピーカ１３、及びマイク１４を含む。電子デバイス２ａの様々なコンポーネントは、メモリに格納された機械語を実行するプロセッサ１０の制御のもと動作する。ユーザインタフェース１２は、タッチスクリーンディスプレイとして視覚ディスプレイと統合されてよい。他の例では、ユーザインタフェース１２は、視覚ディスプレイから切り離された専用のキーパッドであってよい。これらのコンポーネントを含む電子デバイスは当業者には周知であるので、これらはここで詳細に説明される必要はない。ユーザＰＣ２ｂが類似の機能を有することが理解されるであろう。
【００２９】
更に、電子デバイス２ａは、位置決定手段１５、マッピング又はナビゲーションモジュール１６、及び位置特定モジュール１１を備える。ナビゲーションモジュール１６及び位置特定モジュール１７は、位置決定手段１５から位置情報を受けるよう構成されている。示された例において、位置決定手段１５は、いわゆるＧＰＳなどのグローバルポジショニングシステムである。他の例では、種々の衛星利用ナビゲーションシステムが使用されてよい。ナビゲーションモジュール１６及び位置特定モジュール１７は、専用のハードウェアを備えてよい、又は、電子デバイス２ａのプロセッサ１０において動作するソフトウェアプログラム又はアプリケーションを備えてよい。いくつかの例では、ユーザＰＣ２ｂは、位置決定手段１５を備えなくてよい。いくつかの例では、位置決定手段を備えないユーザＰＣ２ｂは、依然として、電子デバイス２ａの位置決定手段などの別個の位置決定手段から位置情報にアクセスしてよい。
【００３０】
位置特定モジュール１７は、位置決定手段１５によって提供された位置情報を使用して位置ベースのサービスをユーザに提供する。
【００３１】
明確にするために、位置決定手段１５を備える電子デバイス２ａを有するシステム１の動作が議論される。
【００３２】
一般的に言えば、電子デバイス２ａ又はＰＣ２ｂは、一実施形態において、デバイスそれ自体の位置、又は、ユーザによって選択された位置の地理座標をマッピング又はナビゲーションモジュール１６において決定するよう構成されている。これらの数値座標は、次に、電子デバイス２ａ若しくはＰＣ２ｂそれ自体において、又は、出願人の国際（ＰＣＴ）特許出願番号ＰＣＴ／ＧＢ２０１４／０５１１５２に開示されている態様でサーバ３を用いて、若しくは任意の他の適切なそのようなシステムを用いて、単語ベースの一意の位置識別子に解決され得る。 
【００３３】
本明細書において開示される方法は、しかしながら、単語ベースの地理的位置識別子に限定されるのではなく、容認できる単語の辞書又はデータストアを有するデバイス又はシステムにおいて任意の入力文字ストリングに対して使用され得る。本発明の文脈において、用語'単語'は、自然言語の単語だけを含むように解釈されるのではなく、任意の入力された文字の、アルファベットの、数字の、又はその他のストリングを含んでよい。当該任意の入力されたストリングは、'単語'、例えば、デバイス又はシステムの辞書又はデータストアの容認できる又は予め定義された文字ストリングのエントリを含む若しくはそれに一致する、又は、辞書又はデータストアの何れかのそのような単語エントリを含む若しくはそれに一致するよう意図されている。
【００３４】
同じ又は別の実施形態において、単独の電子デバイス２ａ若しくはＰＣ２ｂ、又は、サーバ３と通信する電子デバイス２ａ若しくはＰＣ２ｂは、複数語文字ストリングであることが好ましい受け付けられた文字の入力ストリングを地理的位置座標のセットなどの関連付けられた側面に解決するよう構成されている。位置ではないものに基づくいくつかの実施形態では、受け付けられた文字の入力ストリングは、検索クエリ又は製品識別子、例えば、バーコード番号又は同様のものなどの関連付けられた側面に解決される。 
【００３５】
以下の説明では、複数語入力ストリングを含む入力ストリングについて言及するが、本発明が、複数語入力ストリングの処理だけに限定されるのではなく、任意の入力ストリングを処理するよう構成され得ることが理解されるであろう。 
【００３６】
電子デバイス２ａ及び／又はＰＣ２ｂは、単独で、又はサーバ３と通信して複数語入力ストリングを受け付け、受け付けられたｎ語の入力ストリング（ここでｎ＝ｘ）のn語の各々について、ａ）ｑ語の辞書からｍ個の単語の候補を選択するよう構成されている。ここで、ｎ、ｍ、及びｑは、正の整数を含み、ｎは、２より大きいか又はそれに等しく、ｍは、ｑより小さい。ｍ及びｎは、ｑより一桁又は数桁小さいのが好ましい。例えば、ｑ語の辞書を有する実施形態では、ｑは、例えば４０，０００であり、ｎは、２又は３ほどの小ささであってよく、ｍは、１００より大きくなく、好ましくは３０ほどの小ささであってよい。ｑ語の辞書は、容認できる単語の固定されたリストを備える、すなわち、辞書はサイズが定期的に変更されてよいが、その内容及び／又はサイズは動的に変化しないのが好ましい。辞書の単語のリストは、アルファベット順及び／又は番号順などの規定された順序で配置されるのが好ましい。 
【００３７】
当該方法は、ｂ）結果として得られたｍｎ個の単語の候補の組み合わせから、単語の組み合わせの候補のサブセットｐを選択する段階を含む。ここで、ｐは、正の整数であり、ｐは、ｍｎより小さい。ｐは、ｑより小さくてよい。ｑが４０，０００である例では、ｎは、例えば３であり、ｍは、１００であり、ｐは、好ましくは約１０００である。４０，０００個の単語について６４兆個の考えられる３語の組み合わせがある本例において、当該方法は、選択された３語の組み合わせの候補の数を、更に検討すべくまず１００３個、すなわち１００万個に低減し、これは次に、ユーザに提示するための、例えば１０ほどの少なさの最終的な候補リストによる更なる処理のために、更に約１０００個の組み合わせの候補に低減される。 
【００３８】
本発明の方法において、段階ａ）は、受け付けられたｎ語の入力ストリングのn語の各々について、固定辞書のｑ語の一部又は全部の各スコア又はランキングを決定又は割り当てて、それにより、最高のスコア又はランキングに基づいて、受け付けられたｎ語の入力ストリングのn語の各々について、ｑ語の固定辞書からｍ個の単語の候補を選択する段階を備えてよい。受け付けられたｎ語の入力ストリングのn語の各々についての、固定辞書のｑ語の一部又は全部のスコア又はランキングは、受け付けられたｎ語の入力ストリングのn語の各々の文字ストリングと、固定辞書のｑ語の一部又は全部の文字ストリングとの間の比較に基づく文字ベースの距離スコアを含んでよい。文字ベースの距離スコアは、編集距離スコアを含んでよいが、操作としての転置による重み付きレーベンシュタイン編集距離スコアなどの重み付き編集距離スコアを含むのが好ましい。
【００３９】
従って、当該方法は通常、誤った形の入力データの修正を備えると見なされ得、ここで、当該入力データは、各単語が、容認できる単語の辞書又はデータストアにおいて組み立てられる、容認できる、又は予め定義された文字ストリング（単語）群に一致するよう意図されている。 
【００４０】
本発明の技術の動機になる技術的問題は、ユーザが何を入力するつもりだったかもしれないのかを判断するために使用され得る要因の数を特定することは可能だが、上述の例の６４兆個の考えられる３語の組み合わせが逐次処理され、１つ又は複数の単語の組み合わせの候補を意図された入力であると特定して誤った形の入力ストリングを置き換えた、又は置き換えるべく選択されたならば、例えばＰＣにおいて動作するプロセスは、動作するのに宇宙が始まって以来の時間より長くかかるであろう。 
【００４１】
実際には、一般的な水準で、本発明の方法は、意図された可能性のある複数語の組み合わせのスコア又はランキングを改善するために使用され得る一連の方法を、それらのおおよその速さの観点から使用する段階を備える。次に、これらの方法の中から第１の最も速い方法が、全ての考えられるものに対して適用される。次に、この段階において最良と思われる例えば１００万個の考えられるものが選択され、その他のものは全て破棄され、それにより、更に検討すべく、考えられる候補を実質的に'選りすぐる'。これに続いて、１００万個の考えられるもののスコア又はランキングの品質を調整し、ひいては改善するために、第２の、おそらくより遅いであろう方法が適用され、これらから、この段階において最良と思われる例えば１，０００個の考えられるものが選択され、その他のものは全て破棄される。当該方法は次に、これら１０００個の考えられるもののスコアの品質を調整し、ひいては改善するために、第３の、おそらく最も遅いであろう方法を適用する段階を含んでよく、これにより、１０００個の候補のうちの予め定められた少数、例えば１０個の選択、又は、１又は複数の基準を満たす低減された数の候補うちの当該１０００個の候補からの選択がもたらされ、この段階において最良と思われる少数の候補が提供され、その他のものは全て破棄されてよい。そのような方法は、何兆個もの考えられる組み合わせを処理する必要性をなくし、実際には、段階的な選択プロセスを通して迅速かつ計算効率よく、非常に少数の単語の組み合わせの候補にたどり着き、当該非常に少数の単語の組み合わせの候補は、それらの一意の側面に解決され得、誤った形の入力データの考えられる候補として１又は複数がデバイス又はシステムのユーザに提示され得る。
【００４２】
この技術が機能する鍵は、第１の方法が、不正確であると見なされることもあるが、最終的な少数の、例えば１０個の最良な組み合わせの候補のうち１つが、第１の方法だけで計算された例えば上位１００万個の考えられるもの以外に存在するということは極めて起こりそうにないほど十分正確であるいうことである。第２の方法は、不正確と見なされることもあるが、１０個の最良の考えられるもののうち１つが、第１の方法及び第２の方法によって共同で計算された例えば上位１，０００個の考えられるもの以外に存在するということは極めて起こりそうにないほど十分に正確である。そしてそのように続く。 
【００４３】
上記の例は、３つの方法を連続して適用することについて述べたが、入力の種類、及び、電子デバイス２ａ、ＰＣ２ｂ、及び／又はサーバ３における計算効率のために要求される選りすぐりの程度に応じて、２つの方法ほどの少数の方法があってよい、又は、３つの方法より多くの方法があってよいことが理解されよう。
【００４４】
辞書サイズがｑ＝４０，０００であり、単語群サイズがｎ＝３であり、３語の群における単語又はスロットごとの選択された候補が、ｍ＝１００を含む上述の例で考えると、４０，０００語の辞書における６４兆個の考えられる３語の群の全てに対して、どの計算効率的な方法も明示的に及び個々に適用され得ないことは明らかである。しかしながら、明示的に又は暗黙的に、考えられるものに含まれる３語の各々について良好さの程度又は'スコア'を、好ましくはより低いスコアをより良好と見なして計算し、次に、当該程度を好ましくは追加することによって組み合わせることにより、６４兆個の考えられるもの全てについて何らかの良好さの程度、例えばスコア又はランキングを効率よく計算することが可能である。３語の群の各'スロット'に入り得る、考えられる単語は４００００個だけなので、これは、多くても３×４００００回の計算を伴う。次に、後に更に詳細に説明されるように、最高の、すなわち最も低いスコアを有する６４兆個の考えられるもののサブセットを選び出すよう、類似した暗黙的なプロシージャを使用することが可能である。 
【００４５】
６４兆個の考えられる３語の組み合わせのサブセットを選び出す方法は、以下の段階を備えてよい。
Ｉ．電子デバイス２ａ又はＰＣにおいて受け付けられた３語の入力の各単語について、辞書内の例えば３０個又はそれより多くの、タイポグラフィカルに（ｔｙｐｏｇｒａｐｈｉｃａｌｌｙ）、音声的に、又は近似音声的に（ａｐｐｒｏｘｉｍａｔｅ−ｐｈｏｎｅｔｉｃａｌｌｙ）最も類似した単語を選ぶ。このことは、特定のスコアに応じて辞書の単語を効果的にランク付けすることによって行われてよい。これは、上記辞書語と受け付けられた入力単語との間の、又は、上記辞書語の音声的又は近似音声的表現と入力単語との間の重み付きレーベンシュタイン編集距離であることが好ましい。ここでは用語'効果的'が使用される。なぜなら、常に全ての単語についてスコアを明示的に計算する必要があるわけではないからである。何れにしても、当該方法は、最適なスコアを有する３０個又はそれより多くの単語が、受け付けられた入力文字ストリングのn語の各々についてのｍ個の単語の候補として特定されることを可能にする。当該方法は、隣接する文字の転置を考慮する重み付きレーベンシュタイン編集距離の標準的な変形物を利用するのが好ましい。編集距離の重みは、技術的及び経験的な基準に応じて慎重に選択されるのが好ましい。
【００４６】
例：受け付けられた'ｍｅｏ．ａｍｍｏｕｎ'，' ｎａｉｌｄ'という誤った形の入力単語群ストリングを例にとると、誤った形の受け付けられた入力単語'ｍｅｏ'について、ユーザが'ｍｅｏ'の代わりにタイプするつもりだったかもしれないものの候補として、辞書内のタイポグラフィカルに、音声的に、又は近似音声的に最も類似した単語は、とりわけ以下の考えられるものをもたらす。それらは、結果として得られたそれらの重み付きレーベンシュタイン編集距離と共に示されている。
［ｍｅｍｏ：１，ｖｅｔｏ：２，ｍｏｎｏ：２，ｒｅｄｏ：２，ｍｏｊｏ：２，...］（１，２，...は、実際の類似度スコアである）
'ａｍｍｏｕｎ'，'ｎａｉｌｄ'について、ｍ個の考えられる単語の候補は、以下を含む。
［ａｍｏｕｎｔ：２，ｍａｍｍｏｔｈ：３，ｈａｍｍｏｃｋ：３，ｌｅｍｏｎ：３，ｆａｍｏｕｓ：３，...]
［ｎａｉｌｓ：１，ｎａｉｌｅｄ：１，ｎａｉｌ：１，ｒａｉｌｅｄ：２，ｓｎａｉｌ：２，...]
【００４７】
ＩＩ．３語の入力群についての単語の候補の３つのリストは、意図された入力ストリングだったかもしれないものについての、一部又は全部の考えられる３語の提案又は候補を取得するために組み合わせられる。各単語について、３０個と３００個との間の何れかの個数の考えられるものが存在するので、これは、意図された入力ストリングについて、３０×３０×３０個から３００×３００×３００個の考えられる単語の組み合わせの候補を生じる。これらの提案は、次にそれら自体にスコア又はランキングを割り当てられるのが好ましく、各提案のスコア又はランキングは、各組み合わせ内の３語の既に決定されたスコア又はランキングを足し合わせることによって取得されるのが好ましい。例えば、ｍｅｍｏ．ａｍｏｕｎｔ．ｎａｉｌｓは、スコア４（１＋２＋１＝４）を有し、ｖｅｔｏ．ａｍｏｕｎｔ．ｎａｉｌｓもまた、スコア４（２＋２＋１＝４）を有する、等である。
【００４８】
考えられるものの全部又は一部の組み合わせられたリスト、すなわち、単語の組み合わせの候補は、スコア又はランキングによってソートされるのが好ましく、これが行われた場合、本例の方法において最も高いスコア又はランキングを有する最悪の提案は、次に破棄され、それにより、更に検討すべく、単語の組み合わせの候補の数を一桁又は数桁分、実質的に低減するのが好ましい。全ての単語のスコアを計算する必要はなくてよいことが理解されるであろう。比較的高いスコア又はランキングを有すると事前に見なされ得る単語をスコア付け又はランク付けする必要はない。比較的高いスコア又はランキングは、それらの単語、又はそれらの単語を含む単語のあらゆる組み合わせが有望ではない候補であると示しているであろう。
【００４９】
段階ＩＩの前に、任意選択の段階ＩＡが、元の単語の各々と共に単語リストにコンパクトに格納されるのが好ましい予め計算された変形語のリストを使用して、形態的に関連する各単語の候補の変形語を追加する。故に、例えば、'ｍｅｍｏ'について、変形語の'ｍｅｍｏｓ'が追加されてよく、'ａｍｏｕｎｔ'について、変形語'ａｍｏｕｎｔｓ'、'ａｍｏｕｎｔｅｄ'及び'ａｍｏｕｎｔｉｎｇ'が追加されてよい。この種の置き換えは、スコアペナルティを受けるのが好ましい。例えば、ペナルティが５である場合、'ｍｅｍｏ'はスコア１を有するので、'ｍｅｍｏｓ'はスコア６を有するであろう。
【００５０】
また、段階ＩＩの前の更なる任意選択の段階ＩＢとして、並べ換えられた変形語（例えば、'ａｍｏｕｎｔ．ｍｅｍｏ．ｎａｉｌｓ'）が追加されてよい。なぜなら、ユーザは、それらのうちの１又は複数をミスタイプするのみならず語順を記憶し間違えているかもしれないからである。これらにもまた、上記のように適切なスコアペナルティが与えられる。 
【００５１】
段階ＩＩにおいて、更に検討すべく単語の組み合わせの候補の数を一桁又は複数桁分、実質的に低減したので、任意選択の段階ＩＡ及び／又はＩＢの有無にかかわらず、更に検討される候補数を更に低減するよう、１又は複数の更なる'選りすぐる'段階が適用されてよい。 
【００５２】
複数語群を地理的位置の入力として利用するデバイス又はシステムの場合では、更なる１又は複数の選りすぐる段階は、以下の段階のうちの１又は複数を含んでよい。
【００５３】
ＩＩＩ．出願人の先に開示された特許出願に開示されている主アルゴリズム、又は任意の他の適切な位置変換アルゴリズムを使用して各複数語（３語）の候補の位置を計算し、次に、当該位置から、電子デバイスの現在の又は最新の既知の位置、又はユーザによって選択された位置などの既知の位置までの距離を決定又は計算する段階。各３語の組み合わせの候補に対してペナルティスコアが距離に比例して追加される。当該ペナルティスコアは、既知の位置、又はユーザによって選択された位置までの距離についての単調増加関数であってよい。及び／又は、
ＩＶ．ある特定の場合のみについて、各３語の提案の位置と、道路若しくは建物などの最も近い地図上の地物、又は他の何らかの選択された地図上の地物との間の距離を見つける。次に、単語群の組み合わせの各候補のスコアが、距離が増加するにつれ増加するペナルティを追加することによって調整され、ペナルティスコアはまた、距離の単調増加関数であってよい。
【００５４】
段階ＩＩＩ及びＩＶは、段階Ｉ及びＩＩ（及び、場合により、更に段階ＩＡ及び／又はＩＢ）の後に別々に適用されてよい、又は、段階ＩＩＩ及びＩＶは組み合わせて適用されてよい。何れにしても、一旦あらゆるペナルティスコアが追加されると、低減された数の単語群の組み合わせの候補、及び／又はそれらの解決された位置が並べ換えられてよく、これらの一部又は全部が、当該並べ換えられた形態で、最も低いスコアを有する候補が第１番目に又は最も目立つように提示又は表示されて、電子デバイス２ａ又はＰＣ２ｂにおいて提示されてよい。それらの候補は、ユーザが選択し、その選択の結果を呼び出し得るように表示されることが好ましい。 
【００５５】
単語の候補のスコア付けは、編集距離スコアに基づいているのが好ましいが、他のスコア付けのメカニズムが利用されてよい。編集距離のスコア付けの場合では、２つの単語ストリングの間の編集距離を計算するための標準的な方法があり、例えば、ｈｔｔｐ：／／ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／Ｅｄｉｔ＿ｄｉｓｔａｎｃｅを参照されたい。公知の方法に伴う技術的問題は、完全に正確になるよう、それが、数千の単語を含む可能性がある辞書の各単語と入力単語ストリングとの比較を要求することである。通常の方法は、各辞書語と誤った形の入力単語ストリングとを比較し、次に、各比較についての適切な編集距離計算を取得する段階を備える。われわれの例において、これは、４０，０００回の別個の編集距離プロシージャの呼び出しを含むかもしれないので、本発明の目的にとってはあまりにも計算上非効率的である。処理速度を上げる他の考えられる代替的な方法は、本発明の目的にとっては依然遅すぎ、更には、望ましくないほど大量のメモリを使用する。
【００５６】
任意の所与の入力単語ストリングの単語、又は入力ストリングの一部に'最も近い単語'を計算するための、この問題に対する解決策は、ごく少量のメモリを利用し、出願人の"Ａ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｓｕｇｇｅｓｔｉｎｇ  Ｃａｎｄｉｄａｔｅ  Ｗｏｒｄｓ  ａｓ  Ｐｏｓｓｉｂｌｅ  Ｒｅｐｌａｃｅｍｅｎｔｓ  ｆｏｒ  ａｎ  Ｉｎｐｕｔ  Ｓｔｒｉｎｇ  Ｒｅｃｅｉｖｅｄ  ａｔ  ａｎ  Ｅｌｅｃｔｒｏｎｉｃ  Ｄｅｖｉｃｅ"と題する、２０１５年１月６日出願の同時係属中の特許出願番号ＧＢ１５００１０４．３に説明されている公知の方法のどれよりも処理が少なくとも一桁速い。
【００５７】
当該プロセスは、標準的なやり方で実装された最も長い間使用されていない（ＬＲＵ）キャッシュを使用して、検討される最後の（例えば）８０個の単語の各々についての編集距離プロシージャの結果（すなわち、"単語リストにおける３０個の最も類似した単語"）をキャッシュするのが好ましい。したがって、３語入力ストリングの組み合わせの提案を計算するようシステムが求められ、それらの入力単語の１又は複数がキャッシュにある場合、任意のそのような単語への結果はほとんど無視できるほどの時間で返される。これは、通常１つのクエリと次のクエリとの間で重複する２語の入力ストリングがあるようにユーザが入力ストリングをタイプするとき、結果が更新される場合に特に役に立つ。なぜなら、ユーザは最後の単語のみを編集しているからである。例として、クエリが以下のようなものであった場合、
Ａ．ｍｅｏ．ａｍｍｏｕｎ．ｎ
Ｂ．ｍｅｏ．ａｍｍｏｕｎ．ｎａ
Ｃ．ｍｅｏ．ａｍｍｏｕｎ．ｎａｉ
Ｄ．ｍｅｏ．ａｍｍｏｕｎ．ｎａｉｌ
Ｅ．ｍｅｏ．ａｍｍｏｕｎ．ｎａｉｌｄ
'ｍｅｏ'及び'ａｍｍｏｕｎ'への編集距離結果は、クエリＢ‐Ｅにおいては再計算の必要はない。
【００５８】
次の段階では、標準的なプロシージャは、入力ストリングの３語の各々についての考えられる置き換えの３つのリストを選び、それらを組み合わせて、３語の入力ストリングの全体についての、３語の全ての考えられる提案／組み合わせの候補を取得することであろう。先の例にあるように、３つのスロットの各々について１００個もの考えられるものがある場合、入力全体については、１００×１００×１００個の考えられるものがあるだろう。残念ながら、これ程の多くの考えられるものを作ると、望ましくないほどの量のメモリを使い尽くすのみならず、望ましくないほど遅いということがはっきりと分かる。全ての１００万個の３語の考えられるものを作った後、従来通り、リストをソートし、例えば、１０００個の最良の項目を選んで次の段階に移動するであろうが、再び、これは実際には望ましくないほど遅いということが分かる。
【００５９】
ここでの好適な手法は、明示的な組み合わせを置き換え、例えば、二分ヒープにおいて実装された、優先度付きキューデータ構造を使用する、修正された最良優先探索を備える暗黙的なプロシージャによってプロシージャをソートすることだが、速度について最適化された他の組み合わせの方法が利用されてよい。 
【００６０】
考えられる最適化は、１６個の最上位ビットに距離スコアを有する１つの６４ビットの整数としてエンコードされ得る［スコア、第１単語数値識別子、第２単語数値識別子、第３単語数値識別子］などの形態で、項目を優先度付きキューに挿入することである。これらの整数は、スコアによってソートされるので、それらは、優先度付きキューに直接挿入され得、このことは、記録を含むキューを有するよりはるかに速い。 
【００６１】
上記方法は、入力の特性、すなわち、［ｍｅｍｏ：１，ｖｅｔｏ：２，ｍｏｎｏ：２，ｒｅｄｏ：２，ｍｏｊｏ：２，...］のようなリスト中のスコアが単調に増加しているという事実を活用することによって、標準的な最良優先探索方法を改善し、同じ３語の項目を二回以上キューの中に挿入しようと決して試みないことを確保し得る。これにより、'見られ'たノードのセットに注視し続ける必要性を省き、このことは同様に、アルゴリズムの速度をかなり上げる。
【００６２】
編集距離の好適な変形物があるということは注目に値する。当該変形物は、近傍のキーをたたくことによってユーザがキーをミスタイプする可能性がより高いとき、キーボード上の関連するキーに関するキーの間の距離と、単語の音声的な類似度と、よく起こるミススペルとを考慮に入れる。更に、出願人の先の特許出願において開示されている地理的位置解決方法に関する実施形態では、陸上にあることが知られた位置を含む単語の組み合わせの候補、又は、それらの解決された位置しか返さないことが好まれる。例えば、地理的位置についての容認できる単語の辞書において、２５００１‐４００００番の単語（単語に１から番号をつける）は、海の位置だけに使用されてよい。これらの単語は、陸の位置に使用される１‐２５０００番の範囲の単語に関連し得るとき、以下に説明される変形プロセスにおいて使用されてよいが、任意選択の変形プロセスが省略される場合は、これらの２５００１‐４００００番の単語のスコアを計算する必要はない。
【００６３】
任意選択の変形プロセスにおいて、考えられる候補のセットに変形語を追加することは、その単語が何らかの適法な３語の組み合わせにおいて生じない限り意味がない。 '〜の変形語である'関係は再帰的である、つまり、'ａｍｏｕｎｔｅｄ'が'ａｍｏｕｎｔ'の変形語である場合かつその場合に限り、'ａｍｏｕｎｔ'は'ａｍｏｕｎｔｅｄ'の変形語であるということに留意すれば、辞書内の４００００個の単語の考えられる変形語尾を計算するだけでよいということになる。変形語とは何かという概念は、主観的要素を有し、このため、最良の結果は、プログラム実行中に変形語を計算するのではなく、４００００個の単語の各々についての変形語のリストを予め計算し、アプリケーションの一部としてそれを配布することによって取得されてよい。このことはまた、語尾のデータの品質が、主なアプリケーションプログラムに対して何の変更も要求することなく改善されてよいことを意味している。 
【００６４】
この任意選択の事前計算方法は２つの更なる利点を有する。第１に、プログラム実行中に変形語を計算すると、プログラムの速度を落とすであろう。第２に、それは、大量の追加のコードをプログラムの中に挿入することを含むであろうし、この種のコードの量は、システムに更なる言語が追加されるにつれて増加する必要があるだろう。
【００６５】
語尾をオフラインで計算することに関わる課題が１つある。それは、４００００個の単語の各々についての変形語のリストを作ると、大量の空間を占有することがあるということである。当該空間は、各単語リストについて（言語ごとに１つ）要求され、空間使用量の総計は、望ましくないほどのものであろう。この課題に対する何れの解決策も、それが、所与の単語の変形語のセットの決定を迅速に可能にしなくてはならず、従って、これが'ｚｉｐ'などの圧縮方式を不可能にするという更なる問題に直面する。
【００６６】
この課題に対する１つの解決策は、以下の見解に基づく。 
‐単語リストは広範囲に及んでいる傾向がある。つまり、それらは、典型的な話し手の語彙のほとんど全ての単語を含んでいる。その結果、それら自体が単語リストにある変形語のみを計算することによる性能上の損失は無視できるほどである。
‐'〜の変形語である'関係は、等価関係である、すなわち、それは、再帰的、対称的、及び推移的である。その結果、類似した単語の等価クラスに単語リストを分割することが可能である。単語リストは、一定の順序で区分される。その結果、各単語を、単語リストにおけるその位置を知らせる整数などの数値識別子によって表すことが可能である。つまり、第１番目の単語の'１'、第２番目の単語の'２'、などである。当該解決策は以下を含む。関連語の各クラスについて、架空の例は、
単語３０："ｉｎｄｅｘ"、単語７９２："ｉｎｄｅｘｅｄ"、及び単語３４９６７："ｉｎｄｅｘｉｎｇ" 
であり、単語は何らかの恣意的な順序で、例えば、アルファベット順に配置されている。次に、最後の単語を除いて、順序付けられたリスト内の各単語の番号に対して、当該リスト上のその次の単語の番号を関連付け、最後の単語に対して、第１番目の単語の番号を関連付ける。したがって、例えば、以下を得るであろう。
３０−＞７９２
７９２−＞３４９６７
３４９６７−＞３０
【００６７】
一旦このプロシージャを関連語の全てのクラスに適用すると、１から４０，０００の範囲の各番号を別のそのような番号と関連付ける。この情報は、長さ４０，０００の配列に、極めてコンパクトに格納され得る。各エントリは２バイトを占有するので、配列全体は８０キロバイトしか占有せず、それは、例えば単語リストそれ自体と比較して無視できる量の空間である。
【００６８】
アルゴリズムにおける前の段階は、単語を返すのではなく、それらの単語に関連付けられた番号を返す。単語に関連付けられた番号が与えられれば、次のプロシージャ、すなわち、所与の単語の番号から開始し、関連付けられた番号に移動することを使用して、極めて迅速に、且つ、空間オーバーヘッドなく関連語（の番号）を見つけるのは自明である。その番号から、その関連付けられた番号に移動する。このプロシージャを開始した番号に戻るまで繰り返す。例えば、'ｉｎｄｅｘｉｎｇ'から開始すると、３４９６７−＞３０−＞７９２−＞３４９６７のように進むであろう。このプロシージャ中に出くわした全ての番号は、検討中の元の単語に関連する単語（ｉｎｄｅｘ、ｉｎｄｅｘｅｄ）を表わす。そのような単語は、それらが既に考えられるもののリスト内にない限り、当該リストに追加される。
【００６９】
関連語の追加後、２５００１‐‐４００００の範囲にある単語（例えば上記の'ｉｎｄｅｘｉｎｇ'）は、上記で詳述された理由により破棄されてよい。
【００７０】
前の任意選択の段階と併合されてよい、並べ換えられた変形語に関連する別の任意選択の段階が、最良優先探索プロシージャにおいて使用される暗黙的なグラフを修正する段階を含んでよい。この修正は、所与のｎ語の入力の全ての（ｎ！−１）個の非自明な並べ換えが同じスコアを有するという事実を活用することによって大幅により速く成され得る。ｎ＝３の場合では、非自明な並べ換えの数は５であろう。
【００７１】
地理的位置特定方法に特有の更なる任意選択の距離測定段階において、選択された１０００個の単語の組み合わせの候補の各々の位置を計算するプロセスは、出願人の先の特許出願において開示されているアルゴリズムに、単語それら自体ではなく単語の数値識別子（番号が割り当てられた辞書語リスト）を供給することによって速度が上げられ得るのが好ましい。なぜなら、このことが、元のアルゴリズムの５つの段階のうち１つを省くからである。次に、１０００個の考えられるものの各々のユーザからの距離が、（代替的な方法より計算がより正確でより速い）標準的な球面距離半正矢関数（ｓｐｈｅｒｉｃａｌ  ｄｉｓｔａｎｃｅ  ｈａｖｅｒｓｉｎｅ  ｆｏｒｍｕｌａ）を使用して計算されるのが好ましい。これに続いて、候補のスコアは、ユーザからの距離の適切な関数を追加することによって修正される。これは次の形であるのが好ましい。
定数×ｌｏｇ（１＋ユーザまでの距離）、式中、ユーザまでの距離はメートル単位で測定されるのが好ましい。
【００７２】
現在のところ、１０００個の考えられるもののリストをソートし、１０個の最良の選択肢を選び、これらを次の段階に伝えることは従来通りのことであろう。実際には、これは、十分に速いと分かった。そうではない場合（例えば、将来'１０００'がより大きい数に置き換えられた場合）、優先度付きキューを使用して、任意の所与の段階において１０個の最良の提案のみに注視し続けることが可能であり、１０００個の項目の最終的なソートの必要性を回避する。
【００７３】
道路などの最も近い地図上の地物までの距離の計算を含む任意選択の距離測定の別の例において、この段階の構造は、'１０００'が例えば'１０'に置き換えられ、まさに上述された前の段階の構造の通りである。 
【００７４】
本明細書において開示された方法では、ほとんどの場合において、ｎ（＝ｘ）個の入力単語の各々についてのｍ個の単語の候補を特定するのに、入力ストリングの単語が、処理されるべき単語の選択の基礎を成すことが想定される。しかしながら、当該プロシージャは、ユーザが、例えば'ｍｅｏ．ａｍｍ．ｕｎ．ｎａｉｌｄ'といった誤った数の疑似単語、すなわち、３つではなく４つの単語を入力した場合に対処すべく修正され得る。入力単語があまりに多い場合、異なる単語は共に'結合'されてよく、次に、本明細書において説明された当該プロシージャが適用されてよい。例えば、当該方法は、'ｍｅｏ＋ａｍｍ．ｕｎ．ｎａｉｌｄ'、'ｍｅｏ．ａｍｍ＋ｕｎ．ｎａｉｌｄ'、'ｍｅｏ．ａｍｍ．ｕｎ＋ｎａｉｌｄ'に適用されてよい。ここで、'＋'は単語セパレータではなく'ダミー'文字である。入力単語あまりに少ない場合、１又は複数の入力単語は異なる位置において分けられてよく、当該方法は、各考えられるものに適用されてよく、この場合も最良の結果を獲得する。
【００７５】
本発明が、図面及び先述の説明において詳細に示され説明されているが、本発明は、特性において例示的であって限定的ではないと見なされるべきであり、例示的実施形態のみが示され説明されており、いかなる方法であっても本発明の範囲を限定しないということが理解される。本明細書において説明された特徴の何れかが、何れかの実施形態で使用されてよいことが理解され得る。例示の実施形態は、互いに排除するものではない、又は、本明細書において記載されない他の実施形態を排除するものではない。従って、本発明はまた、上述された例示の実施形態のうちの１又は複数のものの組み合わせを含む実施形態も提供する。本明細書に記載の本発明に対する変形及び変更が、本発明の主旨及び範囲から逸脱することなく成され得、従って、添付の特許請求の範囲によって示される限定のみが課されるべきである。
【００７６】
次に続く特許請求の範囲において、及び本発明の前述の説明において、言語又は必要な含意を表現するために文脈上他の意味に解すべき場合を除き、単語「備える（ｃｏｍｐｒｉｓｅ）」、又は「備える（ｃｏｍｐｒｉｓｅｓ）」若しくは「備える（ｃｏｍｐｒｉｓｉｎｇ）」などの変形語は、包含的な意味で、すなわち、述べられた特徴の存在を特定するが、本発明の様々な実施形態における更なる特徴の存在又は追加を除外しないように使用される。
【００７７】
何れかの従来技術の公報が本明細書において参照された場合、こうして参照することによって、当該公報が当該技術分野における共通一般知識の一部を形成するものと認めることにはならないことが理解されるべきである。
【図１】
2018506114.tif 000003
【図２】
2018506114.tif 000004
【国際調査報告】
2018506114.tif 000005
2018506114.tif 000006
2018506114.tif 000007