【手続補正書】
【提出日】平成29年10月20日(2017.10.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
モバイル・クライアント・システムに関連付けられた１つまたは複数のプロセッサによる方法であって、
該モバイル・クライアント・システムにおいて、オンライン・ソーシャル・ネットワークの第１のユーザから非構造化テキスト・クエリを受け取る工程と、
該モバイル・クライアント・システムのデータ・ストアからの該オンライン・ソーシャル・ネットワークのソーシャル・グラフの一組のノードにアクセスする工程であって、該ソーシャル・グラフは、複数のノードと、該ノードを接続する複数のエッジと、を含み、該ノードは、
該第１のユーザに対応する第１のノードと、
該オンライン・ソーシャル・ネットワークに関連付けられたコンセプトまたは第２のユーザにそれぞれ対応する複数の第２のノードと、を含む、前記一組のノードにアクセスする工程と、
該モバイル・クライアント・システムのデータ・ストアからの一組の文法テンプレートにアクセスする工程であって、各文法テンプレートは、１つまたは複数の非終端トークンと、１つまたは複数のクエリ・トークンと、を含み、該クエリ・トークンは、０個以上の第２のノードおよび１つまたは複数のエッジに対する参照を含み、各文法テンプレートは、自然言語文字列に基づく、前記一組の文法テンプレートにアクセスする工程と、
該モバイル・クライアント・システムが、該非構造化テキスト・クエリを、アクセスされたノードのうちの１つまたは複数に対してマッチさせること、およびマッチされたノードに対応する非終端トークンを有する該文法テンプレートのうちの１つまたは複数に対してマッチさせることによって、１つまたは複数の構造化クエリを生成する工程であって、各構造化クエリは、該１つまたは複数の非終端トークンとマッチした該アクセスされたノードのうちの１つまたは複数ならびに対応する文法テンプレートにおいて参照される該第２のノードのうちの０個以上および１つまたは複数のエッジに対する参照を含む、前記１つまたは複数の構造化クエリを生成する工程と、
前記モバイル・クライアント・システムが、前記非終端トークンまたはクエリ・トークンのうちの１つに対応していない非構造化テキスト・クエリに少なくとも部分的に基づいて、各文法テンプレートに対するコストを計算する工程と、
該モバイル・クライアント・システムにおいて、１つまたは複数の構造化クエリを該第１のユーザへ表示する工程と、を備え、
表示された構造化クエリのそれぞれは、閾値コスト値より低い計算されたコストを有する、方法。
【請求項２】
前記モバイル・クライアント・システムが、前記非構造化テキスト・クエリを構文解析して１つまたは複数のｎ−ｇｒａｍにする工程、をさらに備え、
各文法テンプレートに対するコストを計算する工程は、前記非終端トークンまたはクエリ・トークンのうちの１つに対応していない該ｎ−ｇｒａｍのうちの１つまたは複数に少なくとも部分的に基づく、請求項１に記載の方法。
【請求項３】
各非終端トークンおよびクエリ・トークンは、関連付けられた挿入コストを有し、
前記コストを計算する工程は、
１つまたは複数のｎ−ｇｒａｍに対応していない前記非終端トークンまたはクエリ・トークンのそれぞれに関する挿入コストを発生する工程を含む、請求項２に記載の方法。
【請求項４】
前記コストを計算する工程は、
前記モバイル・クライアント・システムが、各非終端トークンの該挿入コストに少なくとも部分的に基づいて、特定のｎ−ｇｒａｍに対応する前記非終端トークンのうちの１つまたは複数から特定の非終端トークンを識別する工程を含む、請求項３に記載の方法。
【請求項５】
前記コストを計算する工程は、
前記モバイル・クライアント・システムが、アクセスされたノードのうちの１つを前記非終端トークンのうちの１つへ関連付ける工程と、
該ｎ−ｇｒａｍのうちの１つに対応していない関連付けられたアクセスされたノードに基づいて、前記非終端トークンおよび該関連付けられたアクセスされたノードに関する挿入コストを発生する工程と、を含む、請求項３に記載の方法。
【請求項６】
前記モバイル・クライアント・システムが、関連付けられた文法テンプレートの計算されたコストに少なくとも部分的に基づいて、前記構造化クエリのうちの１つまたは複数をランク付けする工程をさらに備える請求項３に記載の方法。
【請求項７】
前記コストを計算する工程は、
各文法テンプレートに関連付けられた基本コストを発生する工程を含み、
該基本コストは、各文法テンプレートの基礎である１つまたは複数の検索クエリに関連付けられた人気度測定値に対して反比例関係を有する、請求項３に記載の方法。
【請求項８】
前記人気度測定値は、前記第１のユーザの検索クエリ履歴に少なくとも部分的に基づく、請求項７に記載の方法。
【請求項９】
前記人気度測定値は、前記オンライン・ソーシャル・ネットワークのユーザの検索クエリ履歴に少なくとも部分的に基づく、請求項８に記載の方法。
【請求項１０】
前記モバイル・クライアント・システムが、前記第１のユーザから入力を受け取る工程は、
ユーザが文字列をグラフィカル・ユーザ・インターフェース内に入力すると、該文字列の１つまたは複数の文字を受け取る工程を含む、請求項１に記載の方法。
【請求項１１】
前記モバイル・クライアント・システムが、ユーザが該グラフィカル・ユーザ・インターフェース内に１つまたは複数の後続の文字を入力したときに修正された非構造化テキスト・クエリをマッチングすることにより、前記構造化クエリのうちの１つまたは複数を更新する工程をさらに備える請求項１０に記載の方法。
【請求項１２】
前記一組のノードの各ノードは、閾値より大きい係数を有する、請求項１に記載の方法。
【請求項１３】
前記モバイル・クライアント・システムが、所定の間隔で、前記オンライン・ソーシャル・ネットワークから、更新された一組の文法テンプレートまたは更新された一組のノードを受け取る工程をさらに備える請求項１に記載の方法。
【請求項１４】
前記第１のユーザからの表示された構造化クエリのうちの１つの選択に応答して、前記モバイル・クライアント・システムが、選択された構造化クエリを前記オンライン・ソーシャル・ネットワークに送る工程をさらに備える請求項１に記載の方法。
【請求項１５】
前記モバイル・クライアント・システムが、選択された構造化クエリが前記オンライン・ソーシャル・ネットワークへ送られたことに応答して、１つまたは複数の検索結果を受け取る工程をさらに備える請求項１４に記載の方法。
【請求項１６】
前記検索結果のそれぞれは、前記複数の第２のノードのうちの特定の第２のノードに対応する、請求項１５に記載の方法。
【請求項１７】
前記一組のノードは、所定の数のノードからなり、
前記一組の文法テンプレートは、所定の数の文法テンプレートからなる、請求項１に記載の方法。
【請求項１８】
ソフトウェアを具現化する１つまたは複数のコンピュータ可読非一時的記憶媒体であって、前記ソフトウェアは、実行されたとき、モバイル・クライアント・システムが、
モバイル・クライアント・システムにおいて、オンライン・ソーシャル・ネットワークの第１のユーザから非構造化テキスト・クエリを受け取ること、
該モバイル・クライアント・システムのデータ・ストアからの、該オンライン・ソーシャル・ネットワークのソーシャル・グラフの一組のノードにアクセスすることであって、該ソーシャル・グラフは、複数のノードと、該ノードを接続する複数のエッジと、を含み、該ノードは、
該第１のユーザに対応する第１のノードと、
該オンライン・ソーシャル・ネットワークに関連付けられたコンセプトまたは第２のユーザにそれぞれ対応する複数の第２のノードと、を含む、前記一組のノードにアクセスすること、
該モバイル・クライアント・システムのデータ・ストアからの、一組の文法テンプレートにアクセスすることであって、各文法テンプレートは、１つまたは複数の非終端トークンと、１つまたは複数のクエリ・トークンと、を含み、該クエリ・トークンは、０個以上の第２のノードおよび１つまたは複数のエッジに対する参照を含み、各文法テンプレートは、自然言語文字列に基づく、前記一組の文法テンプレートにアクセスすること、
該モバイル・クライアント・システムによって、該非構造化テキスト・クエリを、アクセスされたノードのうちの１つまたは複数に対してマッチさせること、およびマッチされたノードに対応する非終端トークンを有する該文法テンプレートのうちの１つまたは複数に対してマッチさせることによって、１つまたは複数の構造化クエリを生成することであって、各構造化クエリは、該１つまたは複数の非終端トークンにマッチされた該アクセスされたノードのうちの１つまたは複数ならびに対応する文法テンプレートにおいて参照される該第２のノードのうちの０個以上および１つまたは複数のエッジに対する参照を含む、前記１つまたは複数の構造化クエリを生成すること、
前記モバイル・クライアント・システムが、前記非終端トークンまたはクエリ・トークンのうちの１つに対応していない非構造化テキスト・クエリに少なくとも部分的に基づいて、各文法テンプレートに対するコストを計算すること、
該モバイル・クライアント・システムにおいて、１つまたは複数の構造化クエリを該第１のユーザへ表示すること、を行うように動作可能であり、
表示された構造化クエリのそれぞれは、閾値コスト値より低い計算されたコストを有する、１つまたは複数のコンピュータ可読非一時的記憶媒体。
【請求項１９】
１つまたは複数のプロセッサと、該プロセッサによって実行可能な命令を備える該プロセッサに結合されたメモリと、を備えるモバイル・クライアント・システムであって、該プロセッサは、該命令を実行すると、
該モバイル・クライアント・システムにおいて、オンライン・ソーシャル・ネットワークの第１のユーザから非構造化テキスト・クエリを受け取ること、
該モバイル・クライアント・システムのデータ・ストアからの、該オンライン・ソーシャル・ネットワークのソーシャル・グラフの一組のノードにアクセスすることであって、該ソーシャル・グラフは、複数のノードと、該ノードを接続する複数のエッジと、を含み、該ノードは、
該第１のユーザに対応する第１のノードと、
該オンライン・ソーシャル・ネットワークに関連付けられたコンセプトまたは第２のユーザにそれぞれ対応する複数の第２のノードと、を含む、前記一組のノードにアクセスすること、
該モバイル・クライアント・システムのデータ・ストアからの、一組の文法テンプレートにアクセスすることであって、各文法テンプレートは、１つまたは複数の非終端トークンと、１つまたは複数のクエリ・トークンと、を含み、該クエリ・トークンは、０個以上の第２のノードおよび１つまたは複数のエッジに対する参照を含み、各文法テンプレートは、自然言語文字列に基づく、前記一組の文法テンプレートにアクセスすること、
該モバイル・クライアント・システムによって、該非構造化テキスト・クエリを、アクセスされたノードのうちの１つまたは複数に対してマッチさせること、およびマッチされたノードに対応する非終端トークンを有する該文法テンプレートのうちの１つまたは複数に対してマッチさせることによって、１つまたは複数の構造化クエリを生成することであって、各構造化クエリは、該１つまたは複数の非終端トークンにマッチされた該アクセスされたノードのうちの１つまたは複数ならびに対応する文法テンプレートにおいて参照される該第２のノードのうちの０個以上および１つまたは複数のエッジに対する参照からなる、前記１つまたは複数の構造化クエリを生成すること、
前記モバイル・クライアント・システムが、前記非終端トークンまたはクエリ・トークンのうちの１つに対応していない非構造化テキスト・クエリに少なくとも部分的に基づいて、各文法テンプレートに対するコストを計算すること、
該モバイル・クライアント・システムにおいて、１つまたは複数の構造化クエリを該第１のユーザへ表示すること、を行うように動作可能であり、
表示された構造化クエリのそれぞれは、閾値コスト値より低い計算されたコストを有する、システム。