(57)【要約】入力レコメンデーションを確立するデータ処理方法が提供される。方法は、エントリ数分布に基づいた可変プレフィックス長を有する逆牽引を確立し、したがって、確立された逆牽引が、ほとんど使用されない多数の牽引エントリを生成することを防ぎ、作成された入力レコメンデーション牽引の冗長性を減らす。
2017511928.tif 000002
【特許請求の範囲】
【請求項１】
長さが第１の長さ以下であるプレフィックスを、各エントリに対して生成することと、前記プレフィックスを現在のプレフィックスと、また、前記第１の長さを現在の長さと、みなすことと、
複数の現在のプレフィックス内で同じ内容を有するプレフィックスを結合することと、前記結合されたプレフィックスと対応するエントリに対する逆牽引を生成することと、
前記逆牽引内の各プレフィックスによって指されるエントリの各数が、予め設定された値Ｎよりも大きいかどうかを判断することと、
Ｎよりも多い数のエントリを指すプレフィックスが前記逆牽引内に存在する場合、前記逆牽引内のエントリの数がＮよりも大きい前記プレフィックスに対するエントリを切り詰めることと、前記現在のプレフィックスと前記現在の長さとを、プレフィックス長が前記現在の長さに等しく、前記逆牽引内のエントリの数が（Ｎ＋１）であるプレフィックスに基づいて、更新することと、更新された、前記現在のプレフィックスと前記現在の長さとを、前記プレフィックスの前記結合することに、再処理のために戻すことと、
各プレフィックスによって指される前記各エントリの数がＮ以下である場合、前記逆牽引を、入力レコメンデーション牽引として出力することと、
を備える、１つまたは複数のコンピューティングデバイスによって実装される方法。
【請求項２】
前記エントリを、前記逆牽引内のエントリの数がＮよりも大きい前記プレフィックスに対して切り詰めることが、前記逆牽引内のエントリの数がＮよりも大きい前記プレフィックスに対して、前記プレフィックスの長さが前記現在の長さ未満である場合、前記プレフィックスによって指される最初のＮ個のエントリに切り詰めることと、前記プレフィックスの前記長さが前記現在の長さに等しい場合、前記プレフィックスによって指される最初の（Ｎ＋１）個のエントリに切り詰めることと、を含む、請求項１に記載の方法。
【請求項３】
前記現在のプレフィックスと前記現在の長さとを、プレフィックス長が前記現在の長さに等しく、前記逆牽引内のエントリの数が（Ｎ＋１）である前記プレフィックスに基づいて更新することが、１バイトを、プレフィックス長が前記現在の長さに等しく、エントリの数が（Ｎ＋１）である前記プレフィックスに、エントリ内容にしたがって追加して、新しいプレフィックスを形成することと、前記新しいプレフィックスを有するすべてのプレフィックスを、更新された現在のプレフィックスとみなすことと、１増えた前記現在の長さを、更新された現在の長さとみなすことと、を含む、請求項１に記載の方法。
【請求項４】
前記第１の長さの最小値が３である、請求項１に記載の方法。
【請求項５】
Ｎの最小値が５である、請求項１に記載の方法。
【請求項６】
長さが前記第１の長さ以下である前記プレフィックスを、各エントリのために生成する前に、前記エントリを前処理することをさらに含み、前記エントリを前処理することが、
意味のない文字を前記エントリから除去することであって、前記意味のない文字が、空白及び／または句読点を備える、除去することと、
エントリ内容内の、大文字と小文字、また簡体漢字と伝統的な漢字、とを統一することと、
のうちの少なくとも１つを備える、請求項１に記載の方法。
【請求項７】
１つまたは複数のプロセッサと、
メモリと、
前記メモリ内に格納され、長さが第１の長さ以下であるプレフィックスを、各エントリに対して生成し、前記プレフィックスを現在のプレフィックスとみなし、前記第１の長さを現在の長さとみなすために、前記１つまたは複数のプロセッサによって実行可能な、プレフィックス生成部と、
前記メモリ内に格納され、現在のプレフィックス内で同じ内容を有するプレフィックスを結合し、前記結合されたプレフィックスと対応するエントリとに対する逆牽引とを生成するために、前記１つまたは複数のプロセッサによって実行可能な逆牽引生成部と、
前記メモリ内に格納され、前記生成された逆牽引内の各プレフィックスによって指されるエントリの数がＮよりも大きいかどうかを判断し、エントリの前記数がＮよりも大きい場合、処理のために、判断切り詰め部に移動し、各プレフィックスによって指されるエントリの前記数がＮ以下である場合、前記逆牽引を、作成された入力レコメンデーション牽引として出力するために、前記１つまたは複数のプロセッサによって実行可能な第１の判断部と、
前記メモリ内に格納され、前記逆牽引内のエントリの数がＮよりも大きいプレフィックスに対してエントリを切り詰めるために、前記１つまたは複数のプロセッサによって実行可能な前記判断切り詰め部と、
前記メモリ内に格納され、前記現在のプレフィックスと前記現在の長さとを、プレフィックス長が前記現在の長さに等しく、前記逆牽引内のエントリの数が（Ｎ＋１）であるプレフィックスに基づいて更新し、更新された、前記現在のプレフィックスと前記現在の長さとを、再処理のために、前記逆牽引生成部に戻すために、前記１つまたは複数のプロセッサによって実行可能な更新部と、
を備える、システム。
【請求項８】
前記判断切り詰め部が、
前記現在のプレフィックス内の各プレフィックス長が、前記現在の長さ未満かどうかを判断するように構成された長さ判断部と、
プレフィックス長が前記現在の長さ未満であるプレフィックスによって指されるエントリからの最初のＮ個のエントリに、前記長さ判断部の結果に基づいて切り詰めることと、プレフィックス長が前記現在の長さであるプレフィックスによって指されるエントリからの最初の（Ｎ＋１）個のエントリに、前記長さ判断部の前記結果に基づいて切り詰めることと、を行うように構成された切り詰め部と、
を備える、請求項７に記載のシステム。
【請求項９】
前記更新部が、
１バイトを、プレフィックス長が前記現在の長さである前記プレフィックスに、エントリ内容にしたがって、前記長さ判断部の前記結果に基づいて追加して、新しいプレフィックスを形成することと、前記新しいプレフィックスを有するすべてのプレフィックスを、前記現在のプレフィックスとして更新することと、を行うように構成されたプレフィックス更新部と、
前記現在の長さを、更新された現在の長さとして、１増やすように構成された現在の長さ更新部と、
を備える、請求項７に記載のシステム。
【請求項１０】
前記逆牽引生成部が、
すべての現在のプレフィックス内で同じ内容を有する前記プレフィックスを結合するように構成された結合部と、
前記逆牽引を、前記結合されたプレフィックスと前記プレフィックスに対応する前記エントリとに対して生成するように構成された牽引作成部と、
を備える、請求項７に記載のシステム。
【請求項１１】
前記第１の判断部が、
前記逆牽引生成部によって生成された前記逆牽引内で、前記現在のプレフィックス内の各プレフィックスによって指されるエントリの前記数がＮよりも大きいかどうかを、判断するように構成された数判断部と、
前記逆牽引を出力することと、前記数判断部の判断結果に基づいて、各プレフィックスによって指されるエントリの前記数がＮ以下である場合、前記逆牽引生成部の逆牽引結果を出力することと、を行うように構成された出力部と、
を備える、請求項７に記載のシステム。
【請求項１２】
各エントリを前処理するように構成されたエントリ前処理部をさらに備える、請求項７に記載のシステム。
【請求項１３】
１つまたは複数のプロセッサによって実行されると、前記１つまたは複数のプロセッサに、
第１の長さを設定することと、受信クエリ文字列の長さが前記第１の長さより大きいかどうかを判断することと、長さが前記第１の長さ以下であるクエリ文字列に対応する逆牽引を、入力レコメンデーション結果とみなすことと、
長さが前記第１の長さよりも大きいクエリ文字列を、前記第１の長さに基づいて切り詰めることと、
前記切り詰められたクエリ文字列に対応する逆牽引内のエントリの数が、Ｎよりも大きいかどうかを判断することと、エントリの前記数がＮよりも大きい場合、前記第１の長さを更新することと、前記更新された第１の長さを、前記切り詰められたクエリ文字列に対応する前記エントリの数がＮ以下になるまで前記切り詰めることを繰り返すために戻すことと、
前記クエリ文字列の前記長さが前記第１の長さよりも大きく、切り詰められた前記クエリ文字列に対応するエントリの前記数がＮ以下である場合、一致しないエントリをフィルタにかけることと、
前記クエリ文字列の前記入力レコメンデーション結果を出力することと、
を備える動作を実行させる実行可能命令を格納する、１つまたは複数のコンピュータ可読媒体。
【請求項１４】
前記第１の長さを更新することが、１増やした前記第１の長さを前記更新された第１の長さとみなすことを含む、請求項１３に記載の１つまたは複数のコンピュータ可読媒体。
【請求項１５】
前記一致しないエントリをフィルタにかけることが、前記切り詰められたクエリ文字列に対応するすべてのエントリを、前記クエリ文字列と、最初の文字から開始して１文字ずつ比較することと、最初のｘ文字が前記クエリ文字列と同じでないエントリを除去することであって、ｘが前記クエリ文字列の前記長さを表す、除去することと、を含む、請求項１３に記載の１つまたは複数のコンピュータ可読媒体。
【請求項１６】
前記切り詰められたクエリ文字列に基づいて見つけた、前記逆牽引内のすべてのエントリを、前記クエリ文字列と、一文字ずつ比較することが、前記クエリ文字列と前記エントリとの文字が同じ言語でない場合、前記クエリ文字列と前記エントリとを、音標文字に、比較のために、比較プロセス中に変換することを備える、請求項１５に記載の１つまたは複数のコンピュータ可読媒体。
【請求項１７】
前記クエリ文字列の前記入力レコメンデーション結果を出力することが、長さが前記第１の長さ未満である前記クエリ文字列に対して、対応するエントリを、前記クエリ文字列の前記入力レコメンデーション結果として、直接出力することと、前記切り詰めることの後で同じ牽引が見つからなかった時、ヌル値を、前記クエリ文字列の前記入力レコメンデーション結果として返すことと、前記一致しないエントリをフィルタにかけた後の結果を、前記切り詰めることの後に見つけた前記牽引に対する、前記クエリ文字列の前記入力レコメンデーション結果とみなすことと、を含む、請求項１３に記載の１つまたは複数のコンピュータ可読媒体。
【請求項１８】
前記第１の長さの最小値が３である、請求項１３に記載の１つまたは複数のコンピュータ可読媒体。
【請求項１９】
前記動作が、前記逆牽引を生成することをさらに備える、請求項１３に記載の１つまたは複数のコンピュータ可読媒体。
【請求項２０】
前記逆牽引が、エントリの数の分布に基づいた可変プレフィックス長を含む、請求項１３に記載の１つまたは複数のコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
関連特許出願の相互参照
本出願は、参照によりその全体が本明細書に組み込まれる、２０１４年３月６日に出願された、「Ｄａｔａ  Ｐｒｏｃｅｓｓｉｎｇ  Ｍｅｔｈｏｄ  ａｎｄ  Ｓｙｓｔｅｍ  ｏｆ  Ｅｓｔａｂｌｉｓｈｉｎｇ  Ｉｎｐｕｔ  Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ」という題名の、Ｃｈｉｎｅｓｅ  Ｐａｔｅｎｔ  Ａｐｐｌｉｃａｔｉｏｎ  Ｎｏ．２０１４１００８０５６８．９の外国優先権を主張する。
【０００２】
本出願は、検索の分野に関連し、より具体的には、入力レコメンデーションを確立するデータ処理方法とシステムとに関する。
【背景技術】
【０００３】
検索エンジンは、インターネット内の情報リソースを収集し、整理し、また、ユーザに検索能力を提供するためのシステムである。システムは、情報収集と、情報整理と、ユーザクエリとを含む。通常、ユーザは、キーワードを検索エンジン内で入力して検索を行い、検索エンジンは、キーワードに一致するコンテンツをデータベースから見つけて、ユーザにフィードバックする。
【０００４】
最近、多数の検索エンジンは、ユーザの最初の検索クエリに関連する、一連の推奨検索クエリを提供する。この一連の推奨検索クエリは、また、入力レコメンデーションとも呼ばれ、入力ボックス内に現在提供されている部分的な入力に基づいて推薦される、完全な入力文字列に対応する。たとえば、検索エンジンは、テキスト入力を受信するためのクエリ入力エリアを含むことができる。検索サービスは、テキスト入力に対する検索クエリ提案を提供し、ユーザは、検索クエリ提案を、検索クエリ語として選択することができる。入力レコメンデーションは、主に、ユーザによって潜在的に入力される完全なテキストを、既存の部分的な入力にしたがって推奨するためと、ユーザ入力のプロセス中に、ユーザにテキスト入力を迅速に終わらせるように促すためとに、使用される。たとえば、ユーザによって入力された元の検索語が「中」である場合、検索エンジンは、「中国（中国）」、「中心（ｃｅｎｔｅｒ）」、「中医（Ｃｈｉｎｅｓｅ  ｍｅｄｉｃｉｎｅ）」、などの関連検索語を提供することができる。
【０００５】
現在、入力レコメンデーションを提供するための方法は、主に、入力レコメンデーションのためのオフライン牽引を生成することと、オンライン入力レコメンデーションを提供することと、を含む。入力レコメンデーションのためのオフライン牽引を生成することの手順を、また、入力レコメンデーションを作成することと呼ぶことができ、それは、すべてのレコメンデーションエントリに対するすべてのプレフィックスを一覧にすることと、同じプレフィックスを有する異なるエントリを結合することと、プレフィックスを結合させた推奨エントリのための逆牽引を生成することと、各プレフィックスの逆牽引を特定のビジネスニーズにしたがって分類することと、各プレフィックスに対する入力レコメンデーションとして、最も重要な最初のＮ個のエントリに切り詰めることと、プレフィックス牽引を生成することと、を含むことができる。オンライン入力レコメンデーションを提供する手順は、プレフィックス牽引を、テキストボックス内のユーザの現在の入力にしたがって検索することと、牽引レコードをプレフィックス牽引に基づいて返すことと、を含むことができ、牽引レコードは、提供された入力レコメンデーションである。
【０００６】
しかしながら、少なくとも以下の問題が、入力レコメンデーションを確立する既存の技術内に見られる。
【０００７】
推奨エントリの数が比較的多く、各推奨エントリに対するプレフィックスの完全なリストの数もまた多いため、すべての推奨エントリに対して挙げられるすべてのプレフィックスの数は、膨大である。この膨大な数のプレフィックスに基づいて作成される逆牽引内では、多数の牽引エントリ、たとえば、比較的長いプレフィックス長を有するいくつかの牽引エントリは、ほとんど使用されない。比較的短いプレフィックスが、少ない数のエントリを指す場合、作成された牽引は、より長いプレフィックスによって指されるエントリを、完全に含むことができる。したがって、より長いプレフィックスに対応する牽引エントリは、ほとんど使用されない。上記の説明から理解することができる通り、既存の方法にしたがって作成された入力レコメンデーション牽引には、冗長性が存在する。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明の概要は、以下の発明を実施するための形態でさらに説明する概念のうちのいくつかを、簡略化した形式で紹介するために提供される。本発明の概要は、特許請求の主題の、すべての重要な特徴または必須の特徴を特定することを意図せず、また、特許請求の主題の範囲を決定する際の補助として、単独で使用されることも意図しない。たとえば、「手法」という用語は、上記の文脈によって許される通り、また本開示を通して、装置、システム、方法、及び／またはコンピュータ実行可能命令を指すことができる。
【０００９】
本開示は、作成された入力レコメンデーション牽引の冗長度を減らすための、入力レコメンデーションを確立するデータ処理方法とシステムとを提供する。
【課題を解決するための手段】
【００１０】
一実施形態によると、入力レコメンデーションを確立するデータ処理方法は、
長さが第１の長さ以下であるプレフィックスを、各エントリに対して生成することであって、プレフィックスを現在のプレフィックスとみなし、第１の長さを現在の長さとみなす、生成することと、
すべての現在のプレフィックス内で同じ内容を有するプレフィックスを、結合し、結合されたプレフィックスと対応するエントリとに対する逆牽引を、生成することと、
逆牽引内の各プレフィックスによって指されるエントリの各数が、予め設定された値Ｎよりも大きいかどうかを判断することと、
Ｎよりも多い数のエントリを指すプレフィックスが逆牽引中に存在する場合、逆牽引内のエントリの数がＮよりも大きいプレフィックスに対して、エントリを切り詰めることと、現在のプレフィックスと現在の長さとを、プレフィックスの長さが現在の長さに等しく、逆牽引内のエントリの数が（Ｎ＋１）であるプレフィックスに基づいて更新することと、更新された、現在のプレフィックスと現在の長さとを、プレフィックスの結合に、再処理のために戻すことと、
各プレフィックスによって指されるエントリの各数がＮ以下である場合、逆牽引を、入力レコメンデーション牽引として出力することと、を含む。
【００１１】
一実施形態では、逆牽引内でエントリの数がＮよりも大きいプレフィックスに対して、エントリを切り詰めることは、逆牽引内でのエントリの数がＮよりも大きいプレフィックスに対して、プレフィックスの長さが現在の長さ未満である場合、プレフィックスによって指される最初のＮ個のエントリに切り詰めることと、プレフィックスの長さが現在の長さに等しい場合、プレフィックスによって指される最初の（Ｎ＋１）個のエントリに切り詰めることと、を含む。
【００１２】
一実施形態では、現在のプレフィックスと現在の長さとを、プレフィックス長が現在の長さに等しく、逆牽引内のエントリの数が（Ｎ＋１）であるプレフィックスに基づいて更新することは、１バイトを、プレフィックス長が現在の長さに等しく、エントリの数が（Ｎ＋１）であるプレフィックスに、エントリの内容にしたがって追加して、新しいプレフィックスを形成することと、新しいプレフィックスを有するすべてのプレフィックスを、更新された現在のプレフィックスとみなすことと、１増加した現在の長さを、更新された現在の長さとみなすことと、を含む。
【００１３】
一実施形態では、第１の長さの最小値は、３である。
【００１４】
一実施形態では、Ｎの最小値は、５である。
【００１５】
一実施形態では、長さが第１の長さ以下であるプレフィックスを、各エントリに対して生成する前に、方法は、さらに、エントリを前処理することをさらに含み、エントリを前処理することは、
意味のない文字をエントリから除去することであって、意味のない文字が、空白及び／または句読点を備える、除去することと、
エントリ内容内の大文字と小文字、簡体漢字と伝統的な漢字、とを統一することと、
のうちの少なくとも１つを備える。
【００１６】
別の実施形態によると、入力レコメンデーションを確立するデータ処理システムは、プレフィックス生成部と、逆牽引生成部と、第１の判断部と、判断切り詰め部と、更新部と、を含み、
プレフィックス生成部は、長さが第１の長さ以下であるプレフィックスを、各エントリに対して生成することと、プレフィックスを現在のプレフィックスとして、第１の長さを現在の長さとして、みなすことと、を行うように構成され、
逆牽引生成部は、現在のプレフィックス内で同じ内容を有するプレフィックスを結合することと、結合されたプレフィックスと対応するエントリとに対する逆牽引を生成することと、を行うように構成され、
第１の判断部は、生成された逆牽引内の各プレフィックスによって指されるエントリの数が、Ｎよりも大きいかどうかを判断することと、エントリの数がＮよりも大きい場合、判断切り詰め部に、処理のために移動することと、各プレフィックスによって指されるエントリの数がＮ以下である場合、逆牽引を、作成された入力レコメンデーション牽引として出力することと、を行うように構成され、
判断切り詰め部は、逆牽引内のエントリの数がＮよりも大きいプレフィックスに対して、エントリを切り詰めるように構成され、
更新部は、現在のプレフィックスと現在の長さとを、プレフィックス長が現在の長さに等しく、逆牽引内のエントリの数が（Ｎ＋１）であるプレフィックスに基づいて更新することと、更新された、現在のプレフィックスと現在の長さとを、逆牽引生成部に、再処理のために戻すことと、を行うように構成されている。
【００１７】
一実施形態では、判断切り詰め部は、長さ判断部と切り詰め部とを備え、
長さ判断部は、現在のプレフィックス内の各プレフィックスの長さが、現在の長さ未満であるかどうかを判断するように構成され、
切り詰め部は、プレフィックス長が現在の長さ未満であるプレフィックスによって指されるエントリからの最初のＮ個のエントリに、長さ判断部の結果に基づいて切り詰めることと、プレフィックス長が現在の長さに等しいプレフィックスによって指されるエントリからの最初の（Ｎ＋１）個のエントリに、長さ判断部の結果に基づいて切り詰めることと、を行うように構成されている。
【００１８】
一実施形態では、更新部は、プレフィックス更新部と現在の長さ更新部とを備え、
プレフィックス更新部は、１バイトを、プレフィックス長が現在の長さに等しいプレフィックスに、長さ判断部の結果に基づいたエントリ内容にしたがって追加して、新しいプレフィックスを形成することと、新しいプレフィックスを有するすべてのプレフィックスを、現在のプレフィックスとして更新することと、を行うように構成され、
現在の長さ更新部は、現在の長さを、更新された現在の長さとして、１増やすように構成されている。
【００１９】
一実施形態では、逆牽引生成部は、結合部と牽引作成部とを備え、
結合部は、すべての現在のプレフィックス内で同じ内容を有するプレフィックスを結合するように構成され、
牽引作成部は、結合されたプレフィックスとプレフィックスに対応するエントリとに対して、逆牽引を生成するように構成されている。
【００２０】
一実施形態では、第１の判断部は、数判断部と出力部とを備え、
数判断部は、現在のプレフィックス内の各プレフィックスによって指されるエントリの数が、逆牽引生成部によって生成された逆牽引内でＮよりも大きいかどうかを判断するように構成され、
出力部は、逆牽引を出力することと、各プレフィックスによって指されるエントリの数がＮ以下である場合、逆牽引生成部の逆牽引結果を、数判断部の判断結果に基づいて出力することと、を行うように構成されている。
【００２１】
一実施形態では、入力レコメンデーションを確立するデータ処理システムは、さらに、エントリ処理部を備え、エントリ処理部は、各エントリを前処理するように構成されている。
【００２２】
さらに別の実施形態によると、入力レコメンデーションを、入力レコメンデーションを確立するデータ処理方法によって作成された牽引に基づいて提供する方法は、
第２の長さを設定することと、受信クエリ文字列の長さが第２の長さよりも大きいかどうかを判断することと、長さが第２の長さ以下であるクエリ文字列に対応する逆牽引を、入力レコメンデーション結果とみなすことと、
長さが第２の長さよりも大きいクエリ文字列を、第２の長さに基づいて切り詰めることと、
切り詰められたクエリ文字列に対応する逆牽引内のエントリの数が、Ｎよりも大きいかどうかを判断することと、エントリの数がＮよりも大きい場合、第２の長さを更新することと、切り詰められたクエリ文字列に対応するエントリの数がＮ以下になるまで切り詰めを繰り戻すために、更新された第２の長さを戻すことと、
クエリ文字列の長さが第２の長さよりも大きく、切り詰められたクエリ文字列に対応するエントリの数がＮ以下である場合、一致しないエントリをフィルタにかけることと、
クエリ文字列の入力レコメンデーション結果を出力することと、を含む。
【００２３】
一実施形態では、第２の長さを更新することは、１増えた第２の長さを、更新された第２の長さとみなすことを含む。
【００２４】
一実施形態では、一致しないエントリをフィルタにかけることは、切り詰められたクエリ文字列に対応するすべてエントリを、クエリ文字列と、最初の文字から開始して一文字ずつ比較することと、最初のｘ文字がクエリ文字列と同じでないエントリを除去することと、を含み、ｘは、クエリ文字列の長さを表す。
【００２５】
一実施形態では、逆牽引内の、切り詰められたクエリ文字列に基づいて見つけた、逆牽引内のすべてのエントリを、クエリ文字列と、一文字ずつ比較することは、クエリ文字列とエントリとの文字が同じ言語でない時、クエリ文字列とエントリとを、比較のための音標文字に、比較処理中に変換すること、を備える。
【００２６】
一実施形態では、クエリ文字列の入力レコメンデーション結果を出力することは、対応するエントリを、長さが第２の長さ未満のクエリ文字列に対するクエリ文字列の入力レコメンデーション結果として、直接出力することと、同じ牽引が切り詰めの後に見つからない時に、ヌル値を、クエリ文字列の入力レコメンデーション結果として返すことと、一致しないエントリをフィルタにかけた後の結果を、切り詰め後に見つけた牽引に対するクエリ文字列の入力レコメンデーション結果とみなすことと、を含む。
【００２７】
一実施形態では、第２の長さを設定することは、第２の長さの値を、第１の長さの値に等しく設定することを備える。
【００２８】
別の実施形態によると、入力レコメンデーションを、入力レコメンデーションを確立するデータ処理システムによって作成された牽引に基づいて提供するシステムは、長さクエリ部と、クエリ文字列切り詰め部と、判断更新部と、フィルタ部と、レコメンデーション出力部とを備え、
長さクエリ部は、第２の長さを設定することと、受信したクエリ文字列の長さが、第２の長さよりも大きいかどうかを判断することと、長さが第２の長さ以下であるクエリ文字列に対応する逆牽引を、入力レコメンデーション結果とみなすことと、を行うように構成され、
クエリ文字列切り詰め部は、長さが第２の長さより大きいクエリ文字列を、第２の長さに基づいて切り詰めるように構成され、
判断更新部は、切り詰められたクエリ文字列に対応する逆牽引内のエントリの数が、Ｎよりも大きいかどうかを判断することと、エントリの数がＮよりも大きい場合、第２の長さを更新することと、クエリ文字列切り詰め部に、切り詰められたクエリ文字列に対応するエントリの数がＮ以下になるまで切り詰めを繰り戻すために、戻ることと、を行うように構成され、
フィルタ部は、クエリ文字列の長さが第２の長さよりも大きく、切り詰められたクエリ文字列に対応するエントリの数がＮ以下である場合、一致しないエントリをフィルタにかけるように構成され、
レコメンデーション出力部は、クエリ文字列の入力レコメンデーション結果を出力するように構成されている。
【００２９】
一実施形態では、判断更新部は、エントリ数判断部と、第２の長さ更新部と、返送部とを備え、
エントリ数判断部は、クエリ文字列切り詰め部によって切り詰められたクエリ文字列に対応する逆牽引内のエントリの数が、Ｎよりも大きいかどうかを判断するように構成され、
第２の長さ更新部は、１を加えた後の第２の長さを、更新された第２の長さとみなすように構成され、
返送部は、エントリの数がＮよりも大きいクエリ文字列を、エントリ数判断部の判断結果と、第２の長さ更新部によって更新された第２の長さとにしたがって、クエリ文字列切り詰め部に戻すように構成されている。
【００３０】
一実施形態では、フィルタ部は、識別変換部と比較フィルタ部とを備え、
識別変換部は、クエリ文字列及びエントリが同じ言語であるかどうかを識別し、違う場合、クエリ文字列またはエントリの言語を変換して、クエリ文字列及びエントリが同じ言語であるようにするように構成され、
比較フィルタ部は、切り詰められたクエリ文字列に対応するすべてのエントリを、クエリ文字列と、最初の文字から開始して一文字ずつ比較することと、一致しないエントリをフィルタにかけることと、を行うように構成されている。
【００３１】
本開示のデータ処理方法及びシステムは、入力レコメンデーション牽引を作成し、プレフィックスとエントリとの間の対応関係を確立した後、同じプレフィックスが指すエントリの数を判断し、同じプレフィックスに関連するエントリの数が大きすぎる場合、プレフィックスをさらに改善するために、プレフィックスのプレフィックス長を増やし、改善されたプレフィックスとエントリとの間の関係を再確立する。このようにして、プレフィックスの長さが増えるにつれて、プレフィックスが指すエントリの数が減り、したがって、エントリ数分布に基づいた可変のプレフィックス長を有する逆牽引を確立し、確立された逆牽引が、ほとんど使用されない多数の牽引エントリを生成することを防ぎ、作成された入力レコメンデーション牽引の冗長性を減らす。
【００３２】
入力レコメンデーションを、本開示内で確立される入力レコメンデーション牽引に基づいて提供する方法及びシステムは、クエリ文字列の長さが第２の長さ以上の時、受信クエリ文字列を、第２の長さにしたがって切り詰め、切り詰められたクエリ文字列に対応するエントリの数がＮよりも大きい場合、第２の長さの値を、クエリ文字列を再度切り詰めるために一時的に増やして、エントリの数がＮ以下であることを確実にし、クエリ文字列の元の長さが第２の長さよりも大きく、見つけたエントリの数がＮ以下である場合、クエリ文字列に一致しないエントリを、比較方法を使用して除去して、エントリが受信クエリ文字列に対応することを確実にする。前述の方法は、プレフィックス長を動的に増やし、したがって、見つけたエントリの数がＮを超えないことを確実にする。したがって、比較を実行することが必要な時の、比較のための計算量を削減することができ、それによって、入力レコメンデーションを提供するための効率を向上させる。
【００３３】
加えて、入力レコメンデーションを作成された入力レコメンデーション牽引に基づいて提供する方法及びシステムは、また、漢字と音標文字との混ざりあった入力の問題を、クエリ文字列とエントリとの内容を比較の前にｕｔｆ−８ユニコードに変換することによって、解決することができる。
【００３４】
例示的な実施形態または既存の技術の説明のために使用される図が、本開示の実施形態または既存の技術における技術的解決策をより明確にするために、本明細書で簡単に説明される。以降に説明する図面は、単に、本開示のいくつかの実施形態である。当業者は、創造的な努力をすることなしに、他の図面をこれらの図面にしたがって取得することができる。
【図面の簡単な説明】
【００３５】
【図１】入力レコメンデーション牽引を確立する例示的なデータ処理方法のフローチャートである。
【図２】入力レコメンデーション牽引を確立する例示的なデータ処理システムの構造図である。
【図３】例示的なデータ処理システムにおける逆牽引生成部の構造図である。
【図４】例示的なデータ処理システムにおける第１の判断部の構造図である。
【図５】例示的なデータ処理システムにおける判断切り詰め部の構造図である。
【図６】例示的なデータ処理システムにおける更新部の構造図である。
【図７】入力レコメンデーションを、作成された入力レコメンデーション牽引に基づいて提供する例示的な方法のフローチャートである。
【図８】入力レコメンデーションを、作成された入力レコメンデーション牽引に基づいて提供する例示的なシステムの構造図である。
【図９】入力レコメンデーションを提供する例示的なシステムの判断更新部の構造図である。
【図１０】入力レコメンデーションを提供する例示的なシステムのフィルタ部の構造図である。
【図１１】図２と図８とで説明する例示的なシステムの構造図である。
【発明を実施するための形態】
【００３６】
本開示の実施形態の技術的解決策の明確で完全な説明が、添付の図面と組み合わせて、本開示の実施形態において行われて、当業者が、本開示の技術的解決策をより良く理解できるようにする。本明細書で説明する実施形態は、本開示の実施形態のほんの一部であり、それらのすべてではない。本開示の実施形態に基づいて、当業者によって、創造的努力をなさずに取得されるすべての他の実施形態は、本開示の保護の範囲内にある。
【００３７】
図１は、本開示による、入力レコメンデーション牽引を確立するデータ処理方法のフローチャートである。図１に示す通り、本開示の入力レコメンデーション牽引を確立するデータ処理方法は、以下を備える。
【００３８】
Ｓ１０１は、長さが第１の長さ以下であるプレフィックスを、各エントリに対して生成し、プレフィックスを現在のプレフィックスとみなし、第１の長さを現在の長さとみなす。
【００３９】
最初に、第１の長さ以下の長さを有するプレフィックスが、各エントリに対して生成される。１つの漢字のｕｔｆ−８ユニコード（８ビットのユニコードトランスフォーメーションフォーマットまたはユニコードと呼ばれる）は、通常、３バイトの長さを有する。たとえば、漢字「中」のｕｔｆ−８ユニコードは、「＼ｘｅ４＼ｘｂ８＼ｘａｄ」である。したがって、第１の長さの値は、一般に、少なくとも３になる。通常、英語の文字は、１バイトの長さを有する。したがって、第１の長さの値が３である時、各エントリの音標文字は、３以下の文字を含むプレフィックスのみを生成することができる。第１の長さ以下の長さを有するプレフィックスは、現在のプレフィックスとみなされ、第１の長さは、現在の長さとみなされる。
【００４０】
エントリ「中国石化（シノペック）」を一例として使用する。３以下の長さを有するプレフィックスは、１つの漢字「中」と、音標文字「ｚｈｏｎｇｇｕｏｓｈｉｈｕａ」中の「Ｚ」と「ＺＨ」と「ＺＨＯ」とを備えることができる。
【００４１】
Ｓ１０２は、すべての現在のプレフィックス内で同じ内容を有するプレフィックスを結合し、現在のプレフィックスと結合後の対応するエントリとに対する逆牽引を生成する。
【００４２】
同じプレフィックスが、異なるエントリに対して存在することがある。生成された逆牽引内のプレフィックスの一意性を確保するために、同じ内容を有する現在のプレフィックスを結合する必要があり、逆牽引は、結合後の現在のプレフィックスに対して生成される。逆牽引は、プレフィックスと、プレフィックスが指すエントリと、を備える。
【００４３】
2017511928.tif 000003
【００４４】
【表１】
2017511928.tif 000004
【００４５】
【表２】
2017511928.tif 000005
【００４６】
表１及び表２内の同じプレフィックスは、結合され、逆牽引が生成される。表３は、生成された逆牽引内の結合されたプレフィックスと、そのプレフィックスが指すエントリとの間の関係を示している。
【００４７】
【表３】
2017511928.tif 000006
【００４８】
Ｓ１０３は、生成された逆牽引内の各プレフィックスが指すエントリの各数が、Ｎよりも大きいかどうかを判断し、エントリの数がＮよりも大きい場合、処理のために、エントリを切り詰める動作を開始し、各プレフィックスが指すエントリの各数がＮ以下である場合、逆牽引を、作成された入力レコメンデーション牽引として出力する。
【００４９】
Ｓ１０３では、Ｎは事前に設定された値であり、Ｎの値を必要に応じて選択することができ、それは、一般に、少なくとも５である。プレフィックスに対応するエントリの数がＮよりも大きい場合、これは、そのプレフィックスに対応する多すぎるレコメンデーションが提供され得、エントリの一部が表示され得ない、ということを示す。したがって、そのようなプレフィックス及びそれによって指されるエントリは、さらなる処理を経る必要があり得る。逆牽引内の各プレフィックスに対応するエントリの各数がＮ以下の場合、これは、各プレフィックスに対応するエントリが、冗長を引き起こさずに、入力レコメンデーションとしての役割を果たすことができる、ということを示す。この場合、逆牽引は、作成された入力レコメンデーション牽引である。
【００５０】
たとえば、表４は、生成された逆牽引内のプレフィックスと、そのプレフィックスによって指されるエントリとの間の関係を示している。Ｎの値が５である場合、プレフィックス「Ｚ」及び「ＺＨ」によって指されるエントリは、それぞれ、表４内の６つである。したがって、２つのプレフィックス及びそれらによって指される各エントリは、両方とも、さらなる処理を経る必要がある。他のプレフィックスによって指されるエントリの数は、５未満であり、したがって、さらなる処理は必要でない。
【００５１】
【表４】
2017511928.tif 000007
【００５２】
Ｓ１０４は、逆牽引内のプレフィックスによって指されるエントリの数がＮよりも大きいプレフィックスについて、エントリを切り詰める。
【００５３】
プレフィックスによって指されるエントリの数がＮよりも大きいプレフィックスについて、Ｓ１０４でエントリを切り詰めることは、プレフィックス長が現在の長さ未満であるプレフィックスによって指されるエントリからの最初のＮ個のエントリに切り詰めることと、プレフィックス長が現在の長さに等しいプレフィックスによって指されるエントリからの最初の（Ｎ＋１）個のエントリに切り詰めることと、を備える。
【００５４】
たとえば、表５は、現在の長さが３の時の、生成された逆牽引内のプレフィックスと、そのプレフィックスによって指されるエントリとの間の関係を示している。切り詰めについての前述の原理に基づいた切り詰め後の結果は、表６に示す通りである。
【００５５】
【表５】
2017511928.tif 000008
【００５６】
【表６】
2017511928.tif 000009
【００５７】
Ｓ１０５は、現在のプレフィックスと現在の長さとを、プレフィックス長が現在の長さに等しく、逆牽引内のエントリの数が（Ｎ＋１）であるプレフィックスとに基づいて更新し、現在のプレフィックスと現在の長さとを、プレフィックスを結合する動作に、更新後の再処理のために戻す。
【００５８】
現在の長さに等しいプレフィックス長と、（Ｎ＋１）に等しい逆牽引内のそのエントリの数と、を有するプレフィックスでは、プレフィックスの内容を、エントリ内容にしたがって１バイト増やす。新しく追加される１バイトは、中国語のプレフィックスに対応する各エントリ内の、プレフィックス内容に隣接する次の１バイトの中国語のｕｔｆ−８ユニコード、または音標プレフィックスに対応する各エントリ内のプレフィックスに隣接する次の音標文字のいずれかであってよい。そのバイトを追加されたプレフィックスは、新しいプレフィックスを形成する。新しいプレフィックスを備えるすべてのプレフィックスは、更新された現在のプレフィックスとみなされ、１増えた現在の長さは、更新された現在の長さとみなされる。更新された現在のプレフィックス及び更新された現在の長さは、プレフィックスを結合する動作に、再処理のために戻される。
【００５９】
2017511928.tif 000010
【００６０】
【表７】
2017511928.tif 000011
【００６１】
入力レコメンデーション牽引を確立する前述のデータ処理方法では、そのＳ１０１〜Ｓ１０５の動作を、コード型表現方法を使用して、簡単に表すことができる。 
Ｌ１：｛第１の長さを設定する。第１の長さは、現在の長さとみなされる。 
Ｌ２：第１の長さ以下の長さを有するプレフィックスを生成する。 
Ｌ３：同じプレフィックス内容を有するプレフィックスを結合する。 
Ｌ４：逆牽引を生成する。 
Ｌ５：逆牽引内で各プレフィックスによって指されるエントリの各数を判断する。 
Ｌ６：｛エントリの数がＮよりも大きい場合、Ｌ８にジャンプする。 
Ｌ７：エントリの数がＮ以下である場合、Ｌ１６にジャンプする。｝ 
Ｌ８：プレフィックスの長さが現在の長さ未満であるかどうかを判断する。 
Ｌ９：｛プレフィックスの長さが現在の長さ未満である場合、
Ｌ１０：最初のＮ個のエントリに切り詰める。 
Ｌ１１：プレフィックスの長さが現在の長さに等しい場合、
Ｌ１２：最初の（Ｎ＋１）個のエントリに切り詰める。｝
Ｌ１３：プレフィックス長が現在の長さに等しく、エントリの数が（Ｎ＋１）に等しいプレフィックスを、逆牽引から選択する。 
Ｌ１４：Ｌ１３で選択したプレフィックスに対して、プレフィックス内容が、１バイト増やされ、現在の長さが、１つ増やされる。 
Ｌ１５：Ｌ３に戻る。｝
Ｌ１６：逆牽引を、作成された入力レコメンデーション牽引として出力する。｝
【００６２】
プレフィックスとエントリとの間の対応関係を確立した後、入力レコメンデーション牽引を確立する前述のデータ処理方法は、同じプレフィックスによって指されるエントリの数を判断し、同じプレフィックスに関連するエントリの数が大きすぎる場合、プレフィックスをさらに改善するために、プレフィックスの長さを増やし、その後、改善されたプレフィックスとエントリとの間の関係を、再確立する。このようにして、プレフィックスの長さが増えるにつれて、プレフィックスによって指されるエントリの数が減り、したがって、エントリ数分布に基づいた可変プレフィックス長を有する逆牽引を形成し、作成された入力レコメンデーション牽引が、ほとんど使用されない多数の牽引エントリを作成することを防ぎ、したがって、作成された入力レコメンデーション牽引の冗長性を減らす。
【００６３】
図２は、本開示による、入力レコメンデーション牽引を確立するデータ処理システムの構造図である。図２に示す通り、入力レコメンデーションを確立するデータ処理システムは、プレフィックス生成部２１と、逆牽引生成部２２と、第１の判断部２３と、判断切り詰め部２４と、更新部２５とを備える。
【００６４】
プレフィックス生成部２１は、長さが第１の長さ以下であるプレフィックスを、各エントリに対して生成することと、そのプレフィックスを現在のプレフィックスとみなすことと、第１の長さを現在の長さとみなすここと、を行うように構成されている。
【００６５】
逆牽引生成部２２は、現在のプレフィックス内で同じ内容を有するプレフィックスを結合することと、結合されたプレフィックスと対応するエントリとに対する逆牽引を生成することと、を行うように構成されている。
【００６６】
第１の判断部２３は、逆牽引生成部２２によって生成された逆牽引内の各プレフィックスが指すエントリの数が、Ｎよりも大きいかどうかを判断することと、各プレフィックスが指すエントリの数がＮ以下である場合、逆牽引を、作成された入力レコメンデーション牽引として出力することと、エントリの数がＮよりも大きい場合、処理のために、判断切り詰め部２４に移動することと、を行うように構成されている。
【００６７】
判断切り詰め部２４は、第１の判断部２３においてプレフィックスが指すエントリの数がＮよりも大きい場合、エントリを切り詰めるように構成されている。
【００６８】
更新部２５は、現在のプレフィックスと現在の長さとを、プレフィックス長が現在の長さに等しく、逆牽引内のエントリの数が（Ｎ＋１）であるプレフィックスにしたがって更新することと、更新された、現在のプレフィックスと現在の長さとを、プレフィックスを結合する動作に、再処理のために戻すことと、を行うように構成されている。
【００６９】
図３は、逆牽引生成部２２の構造図である。図３に示す通り、逆牽引生成部２２は、結合部２２１と牽引作成部２２２とを備える。
【００７０】
結合部２２１は、すべての現在のプレフィックス内で同じ内容を有するプレフィックスを結合するように構成されている。
【００７１】
牽引作成部２２２は、結合されたプレフィックスと対応するエントリとに対応する逆牽引を生成するように構成されている。
【００７２】
図４は、第１の判断部２３の構造図である。図４に示す通り、第１の判断部２３は、数判断部２３１と出力部２３２とを備える。
【００７３】
数判断部２３１は、現在のプレフィックス内の各プレフィックスによって指されるエントリの数が、逆牽引生成部２２によって生成された逆牽引内で、Ｎよりも大きいかどうかを判断するように構成されている。
【００７４】
出力部２３２は、逆牽引を出力することと、数判断部２３１の判断結果において、各プレフィックスが指すエントリの数がＮ以下である場合、逆牽引生成部２２内の逆牽引結果を出力することと、を行うように構成されている。
【００７５】
図５は、判断切り詰め部２４の構造図である。図５に示す通り、判断切り詰め部２４は、長さ判断部２４１と切り詰め部２４２とを備える。
【００７６】
長さ判断部２４１は、各プレフィックの長さが現在の長さ未満であるかどうかを判断するように構成されている。
【００７７】
切り詰め部２４２は、プレフィックス長が現在の長さ未満であるプレフィックスが指すエントリからの最初のＮ個のエントリに、長さ判断部２４１の結果にしたがって切り詰めることと、長さ判断部２４１の結果においてプレフィックス長が現在の長さに等しいプレフィックスが指すエントリからの最初の（Ｎ＋１）個のエントリに切り詰めることと、を行うように構成されている。
【００７８】
図６は、更新部２５の構造図である。図６に示す通り、更新部２５は、プレフィックス更新部２５１と現在の長さ更新部２５２とを備える。
【００７９】
プレフィックス更新部２５１は、１バイトを、プレフィックス長が現在の長さに等しく、エントリの数が（Ｎ＋１）に等しいプレフィックスに、エントリ内容にしたがって追加して、新しいプレフィックスを形成することと、追加されたプレフィックス有するすべてのプレフィックスを、現在のプレフィックスとして更新することと、を行うように構成されている。
【００８０】
現在の長さ更新部２５２は、１増えた現在の長さを、更新された現在の長さとみなすように構成されている。
【００８１】
入力レコメンデーション牽引を確立する前述のデータ処理システムは、入力レコメンデーション牽引を確立するデータ処理方法に対応し、データ処理方法の各動作を実装することができる。データ処理システムによって作成される入力レコメンデーション牽引は、データ処理方法の実装効果を達成することができる。
【００８２】
本開示の入力レコメンデーション牽引を確立するデータ処理方法の第２の実施形態を、以降で紹介する。図１に示す通り、データ処理方法のこの第２の実施形態と第１の実施形態との間の違いは、入力レコメンデーション牽引を確立するデータ処理方法が、さらに、各エントリを前処理することＳ１０６を備えることであり、前処理することは、空白、句読点などの意味のない文字をエントリから削除することと、大文字と小文字、簡体漢字と伝統的な漢字、とを統一すること、たとえば、大文字と小文字とを大文字として統一すること、または簡体漢字と伝統的な漢字とを簡体漢字として統一することと、を含むことができる。たとえば、エントリ「石＿油」を「石油（石油）」に変換することができ、またはエントリ「中國石化」を「中国石化（シノペック）」に変換することができる、などである。本実施形態の他の部分は、データ処理方法の第１の実施形態のそれらと同じであり、本明細書では詳細に説明しない。
【００８３】
本開示の入力レコメンデーション牽引を確立するのデータ処理システムの第２の実施形態を、以降に紹介する。図２に示す通り、入力レコメンデーション牽引を確立するのデータ処理方法の第２の実施形態に対応して、入力レコメンデーション牽引を確立するデータ処理システムの第２の実施形態と第１の実施形態との間の違いは、入力レコメンデーション牽引を確立するのこのデータ処理システムは、さらに、エントリ前処理部２６を備えることである。エントリ前処理部２６は、各エントリを前処理するように構成され、空白、句読点などの意味のない文字をエントリから削除することと、大文字と小文字、簡体漢字と伝統的な漢字、とを統一すること、たとえば、大文字と小文字とを大文字として統一すること、または簡体漢字と伝統的な漢字とを簡体漢字として統一することと、を含む。本実施形態の他の部分は、データ処理システムの第１の実施形態のそれらと同じであり、本明細書では詳細に説明しない。
【００８４】
入力レコメンデーション牽引を確立するデータ処理方法の前述の第２の実施形態では、エントリを前処理する動作が、入力レコメンデーション牽引を確立するデータ処理方法の第１の実施形態に基づいて追加され、したがって、意味のない文字を、作成された入力レコメンデーション牽引から削除し、大文字と小文字、簡体漢字と伝統的な漢字、とを統一し、より正確なデータを、入力レコメンデーション牽引を確立するデータ処理方法に提供する。
【００８５】
それに応じて、入力レコメンデーション牽引を確立するデータ処理システムの第２の実施形態では、エントリ前処理部が、入力レコメンデーション牽引を確立するデータ処理方法の第１の実施形態に基づいて追加され、したがって、データ処理のプロセスを、データ処理方法の第２の実施形態内に実装し、より正確なデータを、入力レコメンデーション牽引を確立するデータ処理方法に提供する。
【００８６】
図７は、本開示の実施形態による、入力レコメンデーションを、作成された入力レコメンデーション牽引に基づいて提供する方法のフローチャートである。図７に示す通り、入力レコメンデーションを、作成された入力レコメンデーション牽引に基づいて提供する方法は、以下を備える。
【００８７】
Ｓ７０１は、第２の長さを設定し、受信したクエリ文字列の長さが第２の長さよりも大きいかどうかを判断し、長さが第２の長さ以下であるクエリ文字列に対応する逆牽引を、入力レコメンデーション結果とみなす。
【００８８】
入力レコメンデーション牽引を確立する方法における第１の長さは、本方法では第２の長さとみなされる。受信クエリ文字列に対応する逆牽引は、クエリ文字列の長さが第２の長さ以下である時に、入力レコメンデーション結果とみなされる。受信クエリ文字列の長さが第２の長さよりも大きい場合、処理のための次の方法ブロックを開始する。
【００８９】
Ｓ７０２は、長さが第２の長さよりも大きいクエリ文字列を、第２の長さにしたがって切り詰める。
【００９０】
第２の長さよりも大きい長さを有するクエリ文字列を、クエリ文字列のための第２の長さにしたがって切り詰めることは、特に、第２の長さより前に配置されているクエリ文字の内容に切り詰めることを備える。
【００９１】
Ｓ７０３は、切り詰められたクエリ文字列に対応する逆牽引内のエントリの数が、Ｎよりも大きいかどうかを判断し、エントリの数がＮよりも大きい場合、第２の長さを更新し、切り詰められたクエリ文字列に対応するエントリの数がＮ以下になるまで、切り詰めを繰り返すために戻る。
【００９２】
Ｓ７０２で切り詰められたクエリ文字列対して、対応するエントリが、逆牽引にしたがって見つけられ、エントリの数がＮよりも大きいかどうかに関する判断が行われる。逆牽引を作成するプロセスにおいて、プレフィックスバイトのさらなる追加が必要なプレフィックスに対して切り詰められたエントリの数が、Ｎ＋１であるために、エントリの数がＮよりも大きい時、これは、プレフィックスの長さをさらに増やすことができるということを示し、第２の長さが、１増やされ、更新された第２の長さとみなされる。エントリの数がＮよりも大きいクエリ文字列及び第２の長さは、その後、Ｓ７０２に戻される。クエリ文字列は、更新された第２の長さに従って再度切り詰めを経験し、第２の長さより前に配置されているクエリ文字列の内容に切り詰める。再度切り詰められたクエリ文字列に対応するエントリが、逆牽引にしたがって見つけられ、見つけたエントリの数がＮ以下になるまで、見つけたエントリの数がＮよりも大きいかどうかに関する判断が行われる。
【００９３】
Ｓ７０４は、第２の長さよりも大きい長さを有し、クエリ文字列が切り詰められた後のエントリの数がＮ以下であるクエリ文字列に対して、一致しないエントリをフィルタにかける。
【００９４】
長さが第２の長さよりも大きく、クエリ文字列が切り詰められた後のエントリの数がＮ以下であるクエリ文字列では、クエリ文字列に対応するエントリが、切り詰めという手段によって見つけられるために、これは、エントリのサブセットが、受信クエリ文字列の完全な内容に対応しないことを引き起こし得る。したがって、逆牽引内のエントリと、クエリ文字列の完全な内容との間の比較が、一致しないエントリをフィルタにかけるために必要になる。具体的には、クエリ文字列の内容が、各エントリの内容と、最初の文字から開始して１つずつ比較される。クエリ文字列の長さがｘであり、エントリ内の最初のｘバイトがクエリ文字列の内容と同一である場合、エントリは、クエリ文字列に対応するエントリであるとみなされる。同一でない場合、エントリは、クエリ文字列に対応しないエントリであるとみなされ、本方法ブロックで除去される。
【００９５】
たとえば、入力レコメンデーション牽引を確立する時に、第１の長さは３に設定され、Ｎの値は６に設定される。プレフィックス「ａｂｃ」に対応する５つのエントリは、「ａｂｃｄ、ａｂｃｅ、ａｂｃｆ、ａｂｃｐ、及びａｂｃｅａ」である。したがって、バイトを追加することによる牽引の再作成が、プレフィックス「ａｂｃ」に対して必要であり、作成された牽引は、「ａｂｃ」→「ａｂｃｄ、ａｂｃｅ、ａｂｃｆ、ａｂｃｐ、及びａｂｃｅａ」という対応関係を含む。クエリ文字列「ａｂｃｅ」を受信すると、第２の長さが最初３に設定され、Ｎの値が６に設定され、したがって、検索を実行するために、クエリ文字列「ａｂｃｅ」内の最初の３バイト「ａｂｃ」に切り詰められて、エントリの数が６未満であることを満たす、対応するエントリ「ａｂｃｄ、ａｂｃｅ、ａｂｃｆ、ａｂｃｐ、及びａｂｃｅａ」を取得する。しかしながら、２つのエントリ「ａｂｃｅ及びａｂｃｅａ」のみがクエリ文字列「ａｂｃｅ」に対応し、一方で、他の３つのエントリ「ａｂｃｄ、ａｂｃｆ、及びａｂｃｐ」は、クエリ文字列「ａｂｃｅ」に対応しない。したがって、「ａｂｃｄ、ａｂｃｆ、ａｂｃｐ」を、本方法ブロックにおいて除去することが必要である。
【００９６】
比較のプロセス中、クエリ文字列とエントリとの文字が同じ言語でない、たとえば、クエリ文字列の文字が中国語であるが、エントリの文字がレターである場合、クエリ文字列とエントリとの内容は、比較を行う前に、音標文字に変換され得る、ということに留意すべきである。
【００９７】
Ｓ７０５は、クエリ文字列の入力レコメンデーション結果を出力する。
【００９８】
Ｓ７０１において長さが第２の長さ未満であるクエリ文字列では、対応するエントリは、クエリ文字列の入力レコメンデーション結果として直接出力される。Ｓ７０３における切り詰めの後に同じ牽引が見つからなかった牽引では、ヌル値が、クエリ文字列の入力レコメンデーション結果として返される。Ｓ７０３における切り詰めの後に見つけた牽引では、Ｓ７０４におけるフィルタ処理の結果が、Ｓ７０４でのフィルタ処理後のクエリ文字列の入力レコメンデーション結果として出力される。
【００９９】
入力レコメンデーションを、確立された入力レコメンデーション牽引に基づいて提供する前述の方法は、クエリ文字列の長さが第２の長さ以上である時、受信クエリ文字列を、第２の長さにしたがって切り詰め、切り詰められたクエリ文字列に対応するエントリの数がＮよりも大きい場合、クエリ文字列を再度切り詰めるために、第２の長さの値を一時的に増やして、エントリの数がＮ以下であることを確実にし、クエリ文字列の元の長さが第２の長さよりも大きく、見つけたエントリの数がＮ以下である場合、クエリ文字列に一致しないエントリを、比較方法を使用して除去して、エントリが受信クエリ文字列に対応することを確実にする。前述の方法は、プレフィックス長を動的に増やし、したがって、見つけたエントリの数がＮを超えないことを確実にする。したがって、比較を実行する必要がある時、比較のための計算量を減らすことができ、それによって、入力レコメンデーションを提供するための効率を向上させる。
【０１００】
加えて、方法は、また、クエリ文字列とエントリとの内容を、比較を行う前に、ｕｔｆ−８ユニコードに変換する場合、漢字と中国語の音標文字との混合入力の問題を解決することができる。
【０１０１】
図８は、本開示の実施形態による、入力レコメンデーションを、確立された入力レコメンデーション牽引に基づいて提供するシステムの構造図である。図８に示す通り、入力レコメンデーションを、確立された入力レコメンデーション牽引に基づいて提供するシステムは、長さクエリ部８１と、クエリ文字列切り詰め部８２と、判断更新部８３と、フィルタ部８４と、レコメンデーション出力部８５とを備える。
【０１０２】
長さクエリ部８１は、第２の長さを設定することと、受信クエリ文字列の長さが第２の長さよりも大きいかどうかを判断することと、長さが第２の長さ以下であるクエリ文字列に対応する逆牽引を、入力レコメンデーション結果とみなすことと、を行うように構成されている。
【０１０３】
クエリ文字列切り詰め部８２は、長さが第２の長さよりも大きいクエリ文字列を、第２の長さにしたがって切り詰めるように構成されている。
【０１０４】
判断更新部８３は、切り詰められたクエリ文字列に対応する逆牽引内のエントリの数がＮよりも大きいかどうかを判断することと、エントリの数がＮよりも大きい場合、第２の長さを更新することと、切り詰められたクエリ文字列に対応するエントリの数がＮ以下になるまで、切り詰めを繰り返すために、クエリ文字列切り詰め部８２に戻すことと、を行うように構成されている。
【０１０５】
フィルタ部８４は、クエリ文字列の長さが第２の長さよりも大きく、切り詰められたクエリ文字列に対応するエントリの数がＮ以下である場合、一致しないエントリをフィルタにかけるように構成されている。
【０１０６】
レコメンデーション出力部８５は、クエリ文字列の入力レコメンデーション結果を出力するように構成されている。
【０１０７】
図９は、判断更新部の構造図である。図９に示す通り、判断更新部８３は、エントリ数判断部８３１と、第２の長さ更新部８３２と、返送部８３３とを備える。
【０１０８】
エントリ数判断部８３１は、クエリ文字列切り詰め部８２によって切り詰められたクエリ文字列に対応する逆牽引内のエントリの数が、Ｎよりも大きいかどうかを判断するように構成されている。
【０１０９】
第２の長さ更新部８３２は、１追加された第２の長さを、更新された第２の長さとみなすように構成されている。
【０１１０】
返送部８３３は、エントリ数判断部８３１の判断によるエントリの数がＮよりも大きいクエリ文字列と、第２の長さ更新部８３２によって更新された第２の長さとを、クエリ文字列切り詰め部８２に戻すように構成されている。
【０１１１】
図１０は、フィルタ部の構造図である。図１０に示す通り、フィルタ部８４は、識別変換部８４１と比較フィルタ部８４２とを備える。
【０１１２】
識別変換部８４１は、クエリ文字列及びエントリが同じ言語かどうかを識別することと、違う場合、クエリ文字列またはエントリの言語を変換して、クエリ文字列及びエントリが同じ言語であるようにするように構成されている。具体的には、クエリ文字列及びエントリは、中国語の音標文字に変換され得る。
【０１１３】
比較フィルタ部８４２は、切り詰められたクエリ文字列に対応する逆牽引内のすべてのエントリを、クエリ文字列と、最初の文字から開始して１つずつ比較することと、一致しないエントリをフィルタにかけることと、を行うように構成されている。
【０１１４】
入力レコメンデーションを、確立された入力レコメンデーション牽引に基づいて提供するシステムは、入力レコメンデーションを、確立された入力レコメンデーション牽引に基づいて提供する方法に対応し、例示的な方法のプロセスを実装して、例示的な方法の技術的効果を達成することができる。
【０１１５】
１９９０年代では、技術的進歩は、ハードウェアの進歩（たとえば、ダイオード、トランジスタ、スイッチ、などの回路構造の進歩）とソフトウェアの進歩（方法／プロセスの進歩）との間で差別化され得た。しかしながら、技術の発展と共に、現在の方法または手順の進歩は、ハードウェア回路構造の直接の進歩として見なされ得る。対応するハードウェア回路構造は、改良された方法または手順をハードウェア回路にプログラミングすることによって取得され得る。したがって、方法と手順との進歩が、ハードウェアモジュールによって達成されないと言うことはできない。たとえば、フィールドプログラム可能ゲートアレイ（ＦＰＧＡ）などのプログラム可能論理回路（ＰＬＤ）は、その論理機能がユーザによってデバイスプログラミングを介して決定され得る、集積回路である。デジタルシステムは、ＰＬＤ上に、設計者によるプログラミングを介して集積され得、設計者は、チップ製造業者に、特定用途の集積回路チップ２を設計し、製造するように依頼する必要はない。さらに、集積回路チップの手作業製造業者は、ほとんど、論理コンパイラソフトウェアの使用により取って代わられ得、論理コンパイラソフトウェアは、プログラム開発とコンパイルとのために使用されるソフトウェアコンパイラに類似している。元のコードは、また、コンパイルの前に特定のプログラミング言語で書かれ得、特定のプログラミング言語は、ハードウェア記述言語（ＨＤＬ）とも呼ばれる。ＨＤＬは、１つの種類のみを有するのではなく、ＡＢＥＬ（Ａｄｖａｎｃｅｄ  Ｂｏｏｌｅａｎ  Ｅｘｐｒｅｓｓｉｏｎ  Ｌａｎｇｕａｇｅ）と、ＡＨＤＬ（Ａｌｔｅｒａハードウェア記述言語）と、Ｃｏｎｆｌｕｅｎｃｅと、ＣＵＰＬ（コーネル大学プログラミング言語）と、ＨＤＣａｌと、ＪＨＤＬ（Ｊａｖａ（登録商標）ハードウェア記述言語）と、Ｌａｖａと、Ｌｏｌａと、ＭｙＨＤＬと、ＰＡＬＡＳＭと、ＲＨＤＬ（Ｒｕｂｙハードウェア記述言語）などの多数の種類を含み、今日最も広く使用されているものは、ＶＨＤＬ（超高速集積回路ハードウェア記述言語）及びＶｅｒｉｌｏｇ２である。当業者は、論理方法と手順とを実装するためのハードウェア回路が、方法と手順とを、集積回路に、前述のハードウェア記述言語を使用して論理的にプログラミングすることによって、容易に取得され得る、ということを理解すべきである。コントローラは、任意の適切な方法で実現され得る。たとえば、コントローラは、マイクロプロセッサまたはプロセッサと、（マイクロ）プロセッサ、論理ゲート、スイッチ、特殊用途向け集積回路（ＡＳＩＣ）、プログラム可能論理コントローラ（ＰＬＣ）、または組込みマイクロコントローラによって実行可能な、（ソフトウェアまたはファームウェアなどの）コンピュータ可読プログラミングコードを格納するためのコンピュータ可読媒体と、を使用することができる。コントローラの例は、以下の、ＡＲＣの６２５Ｄ、ＡｔｍｅｌのＡＴ９１ＳＡＭ、ＭｉｃｒｏｃｈｉｐのＰＩＣ１８Ｆ２６Ｋ２０、Ｓｉｌｉｃｏｎｅ  ＬａｂｓのＣ８０５１Ｆ３２０、のマイクロコントローラを含むが、これらに限定されない。メモリコントローラは、また、メモリデバイスの制御論理の一部として実現され���る。
【０１１６】
コントローラを、純粋なコンピュータ可読プログラミングコードという手段によって実現する以外に、論理プログラミングを方法ブロックに対して実行して、論理ゲート、スイッチ、特殊用途向け集積回路、プログラム可能論理コントローラ、及び組込みマイクロコントローラ、などの形態の、同じ機能のコントローラを実現することができる。したがって、この種のコントローラは、ハードウェア構成要素とみなされ得、さまざまな機能を実現するためにその中に含まれるデバイスは、また、ハードウェア構成要素の内部構造とみなされ得る。さらに、さまざまな機能を実現するためのデバイスは、方法とハードウェア構成要素の内部構造とを実現するためのソフトウェアモジュールとみなされ得る。
【０１１７】
上記の実施形態で具体的に例示されたシステム、デバイス、モジュール、またはユニットは、コンピュータチップまたはエンティティによって実装され得、または特定の機能を有する製品を使用して実装され得る。
【０１１８】
説明を容易にするために、上記のデバイスは、個々に説明するための、機能に基づいた異なるユニットに分けられる。本開示の実装形態では、さまざまなユニットの機能は、１つまたは複数のソフトウェア及び／またはハードウェアで実装され得る。
【０１１９】
前述の実装形態から、本開示が、ソフトウェアと必要な一般的なハードウェアプラットフォームとの観点から実装され得る、ということを、当業者は明確に理解することができる。本理解に基づいて、本開示の技術的解決策は、既存の技術に対する貢献の本質において、またはその一部として、ソフトウェア製品という形態で具現化され得る。典型的な構成では、コンピューティングデバイスは、１つまたは複数のプロセッサ（ＣＰＵ）と、入力／出力インターフェースと、ネットワークインターフェースと、メモリとを含む。コンピュータソフトウェア製品は、（パーソナルコンピュータ、サーバ、またはネットワークデバイス、などであり得る）コンピューティングデバイスに、本開示の実施形態または実施形態の特定の部分で説明した方法を実行するように指示する、複数の命令を含むことができる。コンピュータソフトウェア製品は、メモリ内に格納され得る。
【０１２０】
たとえば、図１１は、上記で説明したシステムなどの例示的なシステム１１００を、より詳細に示している。一実施形態では、システム１１００は、１つまたは複数のプロセッサ１１０１と、ネットワークインターフェース１１０２と、メモリ１１０３と、入力／出力インターフェース１１０４とを含むが、これらに限定されない。
【０１２１】
メモリ１１０３は、揮発性メモリ、ランダムアクセスメモリ（ＲＡＭ）及び／または非揮発性メモリ、たとえば、リードオンリメモリ（ＲＯＭ）またはフラッシュＲＡＭなどのコンピュータ可読媒体という形態を含むことができる。メモリ１１０３は、コンピュータ可読媒体の一例である。
【０１２２】
コンピュータ可読媒体は、永久的または非永久的な種類、取り外し可能または固定の媒体を含むことができ、それは、情報の格納を、任意の方法または技術を使用して達成することができる。情報は、コンピュータ可読コマンド、データ構造、プログラムモジュール、または他のデータを含むことができる。コンピュータストレージ媒体の例は、相変化メモリ（ＰＲＡＭ）、スタティックランダムアクセスメモリ（ＳＲＡＭ）、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、他の種類のランダムアクセスメモリ（ＲＡＭ）、リードオンリメモリ（ＲＯＭ）、電気的消去可能プログラマブルリードオンリメモリ（ＥＥＰＲＯＭ）、クイックフラッシュメモリ、または他の内部ストレージ技術、コンパクトディスクリードオンリメモリ（ＣＤ−ＲＯＭ）、デジタル多用途ディスク（ＤＶＤ）または他の光ストレージ、磁気カセットテープ、磁気ディスクストレージまたは他の磁気ストレージデバイス、または任意の他の非伝送媒体、を含むが、これらに限定されず、これらは、コンピューティングデバイスによってアクセス可能であり得る情報を格納するために使用され得る。本明細書で定める通り、コンピュータ可読媒体は、変調データ信号及び搬送波などの一時的な媒体を含まない。
【０１２３】
メモリ１１０３は、プログラム部１１０５とプログラムデータ１１０６とを含むことができる。一実施形態では、プログラム部１１０５は、プレフィックス生成部１１０７、逆牽引生成部１１０８、第１の判断部１１０９、判断切り詰め部１１１０、更新部１１１１、エントリ処理部１１１２、長さクエリ部１１１３、クエリ文字列切り詰め部１１１４、判断更新部１１１５、フィルタ部１１１６、及び／またはレコメンデーション出力部１１１７を含むことができる。これらのユニットの詳細は、前述の説明内で見つけることができ、したがって、本明細書では重複して説明しない。
【０１２４】
本開示の実施形態を、段階的な方法で説明した。各実施形態で強調された部分は、他の実施形態のそれとは異なる。異なる実施形態における同一または類似の部分は、互いに参照され得る。特に、システム実施形態の説明は比較的簡略であり、それは、それらが方法実施形態に類似しているためであり、関連部分は、方法実施形態の各説明を参照し得る。本開示は、さまざまな普遍的なまたはアプリケーション固有の、コンピュータシステム環境または構成、たとえば、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドデバイスまたはポータブルデバイス、タブレットデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラム可能家電装置、ネットワークＰＣ、小型コンピュータ、大型コンピュータ、前述のシステムまたはデバイスのうちの任意のものを含む分散コンピューティング環境、などに適用可能である。
【０１２５】
本開示は、コンピュータによって実行可能なコンピュータ実行可能命令、たとえば、プログラムモジュールという文脈で説明される。一般に、プログラムモジュールは、特定のタスクを実行する、または特定の抽象データ型を実装する、ルーチン、手順、オブジェクト、構成要素、データ構造、などを備える。本開示は、また、分散コンピューティング環境内で実現され得る。そのような分散コンピューティング環境では、タスクは、通信ネットワークを介して接続された遠隔処理装置によって実行される。分散コンピューティング環境では、プログラムモジュールは、ストレージデバイスを含むローカル及び遠隔のコンピュータストレージ媒体内に配置され得る。
【０１２６】
本開示を、実施形態を使用して説明したが、本開示が、本開示の精神から逸脱せずに、多数の変更物と変化物とを有し、添付の特許請求の範囲が、本開示の精神から逸脱せずに、これらの変更物と変化物とを備えることを意図している、ということを、当業者は理解するものである。
【図１】
2017511928.tif 000012
【図２】
2017511928.tif 000013
【図３】
2017511928.tif 000014
【図４】
2017511928.tif 000015
【図５】
2017511928.tif 000016
【図６】
2017511928.tif 000017
【図７】
2017511928.tif 000018
【図８】
2017511928.tif 000019
【図９】
2017511928.tif 000020
【図１０】
2017511928.tif 000021
【図１１】
2017511928.tif 000022
【国際調査報告】
2017511928.tif 000023