【手続補正書】
【提出日】平成28年5月30日(2016.5.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
コンピューティング・デバイスが、
複数のノードと、前記ノード同士をつなげる複数のエッジとを備えるソーシャル・グラフにアクセスする工程であって、前記ノードのうちの２つの間における前記エッジの各々は、それらの間における１次の隔たり度合いを表しており、前記ノードは、
オンライン・ソーシャル・ネットワークに関連付けられている第１のユーザに対応する第１のノードと、
前記オンライン・ソーシャル・ネットワークに関連付けられているコンセプトまたは第２のユーザに各々対応する複数の第２のノードとを含む、工程と、
前記第１のユーザによって入力された非構造化テキスト・クエリを前記第１のユーザのクライアント・システムから受け取る工程と、
前記非構造化テキスト・クエリに基づき前記ソーシャル・グラフの１以上のエッジおよび１以上の第２のノードを識別する工程であって、識別された前記エッジおよび識別された前記第２のノードの各々は、前記非構造化テキスト・クエリの少なくとも一部に対応している、識別工程と、
複数の文法を有する文法フォレストを含むコンテキストフリー文法モデルにアクセスする工程であって、各文法は１以上の非終端トークンおよび１以上のクエリ・トークンを含み、前記文法フォレストは、複数の非終端トークンおよび複数のクエリ・トークンを含む順序付きツリーとして編成されており、各文法は、非終端トークンを通じて１以上の他の文法に隣接する、編成されたサブツリーである、工程と、
前記ソーシャル・グラフの識別された前記１以上のエッジおよび識別された前記１以上の第２のノードに基づき前記文法フォレストの１以上の文法における１以上のクエリ・トークンを識別する工程であって、識別された各クエリ・トークンは前記ソーシャル・グラフの識別された前記第２のノードまたは識別された前記エッジのうちの１以上に対応する、工程と、
前記文法フォレストの１以上の文法を選択する工程であって、選択された各文法は、前記ソーシャル・グラフの識別された前記エッジおよび識別された前記第２のノードの各々に対応する少なくとも１つのクエリ・トークンを含む、文法選択工程と、
１以上の構造化クエリを生成する工程であって、各構造化クエリは選択された文法に対応し、各構造化クエリは対応する前記選択された文法によって生成される自然言語文字列に基づき、各構造化クエリは前記ソーシャル・グラフの識別された前記エッジおよび識別
された前記第２のノードの各々に対応する少なくとも１つのクエリ・トークンを含む、構造化クエリ生成工程と、
前記クライアント・システムの前記第１のユーザに対し、前記第１のユーザによって入力された前記非構造化テキスト・クエリに応じて、前記第１のユーザに対する表示用に提案されるクエリとして前記構造化クエリのうちの１以上を送信する工程と、を行う方法。
【請求項２】
前記文法選択工程は、
各識別されたクエリ・トークンについて、文法フォレストを横断し、１以上の他の識別されたクエリ・トークンの横断と交わっている１以上の非終端トークンを識別する工程と、
識別された前記非終端トークンに隣接するセマンティック・ツリーにおける前記文法のうちの１以上を選択する工程と、を含む請求項１に記載の方法。
【請求項３】
前記文法選択工程は、
前記非構造化テキスト・クエリに対応するセマンティック・ツリーを生成する工程であって、前記セマンティック・ツリーは交わりトークンおよび１以上のクエリ・トークンを含み、各クエリ・トークンは０以上の非終端トークンによって前記交わりトークンにつながっている、工程と、
前記文法フォレストを分析して、前記セマンティック・ツリーに実質的にマッチする非終端トークンおよびクエリ・トークンの１以上のセットを識別する工程であって、各セットは前記交わりトークンに対応する非終端トークンを有する、工程と、
前記交わりトークンに対応する前記非終端トークンに隣接する前記文法フォレストにおける前記文法のうちの１以上を選択する工程と、を含む請求項１に記載の方法。
【請求項４】
前記非構造化テキスト・クエリに基づきクエリ・コマンドを生成する工程をさらに備える、請求項１に記載の方法。
【請求項５】
前記構造化クエリ生成工程は、
各選択された文法について、該選択された文法に基づき、自然言語文字列を生成する工程であって、前記自然言語文字列は識別された前記１以上のクエリ・トークンを含む、工程と、
各自然言語文字列について、該自然言語文字列に基づき、構造化クエリをレンダリングする工程であって、前記構造化クエリは、識別された前記クエリ・トークンに対応する各識別された第２のノードまたは識別されたエッジへの参照を含む、工程と、を含む請求項１に記載の方法。
【請求項６】
前記非構造化テキスト・クエリは１以上のｎグラムを含み、識別された前記エッジおよび識別された前記ノードの各々は前記ｎグラムのうちの少なくとも１つに対応する、請求項１に記載の方法。
【請求項７】
各ｎグラムが前記第１のユーザによって入力されるテキストの１以上の文字を含む、請求項６に記載の方法。
【請求項８】
各ｎグラムが前記非構造化テキスト・クエリからのｎ個のアイテムの連続したシーケンスを含む、請求項６に記載の方法。
【請求項９】
前記識別工程は、
ｎグラムがエッジまたは第２のノードに対応することを示す各ｎグラムに対するスコアを決定する工程であって、少なくとも１つのスコアは少なくとも１つのエッジに対応して決定され、少なくとも１つのスコアは少なくとも１つの第２のノードに対応して決定され
る、工程と、
エッジしきい値スコアよりよりも高いスコアを有する１以上のエッジを選択する工程であって、識別された前記エッジの各々は前記ｎグラムのうちの少なくとも１つに対応する、工程と、
ノードしきい値スコアよりよりも高いスコアを有する１以上の第２のノードを選択する工程であって、識別された前記第２のノードの各々は識別された前記エッジのうちの少なくとも１つにつながっており、識別された前記第２のノードの各々は前記ｎグラムのうちの少なくとも１つに対応する、工程と、を含む請求項６に記載の方法。
【請求項１０】
各ｎグラムに対する前記スコアは、前記ｎグラムがエッジまたは第２のノードに対応する確率である、請求項９に記載の方法。
【請求項１１】
各選択された文法に対するスコアを決定する工程をさらに備え、
前記構造化クエリ生成工程は、文法しきい値スコアよりも高いスコアを有する各選択された文法に対応する１以上の構造化クエリを生成する工程を含む、請求項１に記載の方法。
【請求項１２】
各文法に対するスコアを決定する工程が、前記第１のノードと、該文法のクエリ・トークンに対応する識別された前記第２のノードとの間における隔たり度合いに基づく、請求項１１に記載の方法。
【請求項１３】
各文法に対するスコアを決定する工程が、該文法のクエリ・トークンに対応する識別された前記エッジに基づく、請求項１１に記載の方法。
【請求項１４】
各文法に対するスコアを決定する工程が、該文法のクエリ・トークンに対応する識別された前記第２のノードにつながっている識別されたエッジの数に基づく、請求項１１に記載の方法。
【請求項１５】
各文法に対するスコアを決定する工程が、前記第１のユーザに関連付けられている検索履歴に基づくか、のうちの１以上である、請求項１１に記載の方法。
【請求項１６】
ソフトウェアを具現する１以上の非一時的コンピュータ可読記憶媒体であって、該ソフトウェアは、実行されるとき、
複数のノードと、前記ノード同士をつなげる複数のエッジとを備えるソーシャル・グラフにアクセスする工程であって、前記ノードのうちの２つの間における前記エッジの各々は、それらの間における１次の隔たり度合いを表しており、前記ノードは、
オンライン・ソーシャル・ネットワークに関連付けられている第１のユーザに対応する第１のノードと、
前記オンライン・ソーシャル・ネットワークに関連付けられているコンセプトまたは第２のユーザに各々対応する複数の第２のノードとを含む、工程と、
前記第１のユーザによって入力された非構造化テキスト・クエリを前記第１のユーザのクライアント・システムから受け取る工程と、
前記非構造化テキスト・クエリに基づき前記ソーシャル・グラフの１以上のエッジおよび１以上の第２のノードを識別する工程であって、識別された前記エッジおよび識別された前記第２のノードの各々は、前記非構造化テキスト・クエリの少なくとも一部に対応している、識別工程と、
複数の文法を有する文法フォレストを含むコンテキストフリー文法モデルにアクセスする工程であって、各文法は１以上の非終端トークンおよび１以上のクエリ・トークンを含み、前記文法フォレストは、複数の非終端トークンおよび複数のクエリ・トークンを含む順序付きツリーとして編成されており、各文法は、非終端トークンを通じて１以上の他の
文法に隣接する、編成されたサブツリーである、工程と、
前記ソーシャル・グラフの識別された前記１以上のエッジおよび識別された前記１以上の第２のノードに基づき前記文法フォレストの１以上の文法における１以上のクエリ・トークンを識別する工程であって、識別された各クエリ・トークンは前記ソーシャル・グラフの識別された前記第２のノードまたは識別された前記エッジのうちの１以上に対応する、工程と、
前記文法フォレストの１以上の文法を選択する工程であって、選択された各文法は、前記ソーシャル・グラフの識別された前記エッジおよび識別された前記第２のノードの各々に対応する少なくとも１つのクエリ・トークンを含む、文法選択工程と、
１以上の構造化クエリを生成する工程であって、各構造化クエリは選択された文法に対応し、各構造化クエリは対応する前記選択された文法によって生成される自然言語文字列に基づき、各構造化クエリは前記ソーシャル・グラフの識別された前記エッジおよび識別された前記第２のノードの各々に対応する少なくとも１つのクエリ・トークンを含む、構造化クエリ生成工程と、
前記クライアント・システムの前記第１のユーザに対し、前記第１のユーザによって入力された前記非構造化テキスト・クエリに応じて、前記第１のユーザに対する表示用に提案されるクエリとして前記構造化クエリのうちの１以上を送信する工程と、を実行するように機能する、媒体。
【請求項１７】
１以上のプロセッサと、前記プロセッサによって実行可能な命令を備え前記プロセッサに結合されているメモリとを備えるシステムであって、前記プロセッサは、前記命令を実行するときに、
複数のノードと、前記ノード同士をつなげる複数のエッジとを備えるソーシャル・グラフにアクセスする工程であって、前記ノードのうちの２つの間における前記エッジの各々は、それらの間における１次の隔たり度合いを表しており、前記ノードは、
オンライン・ソーシャル・ネットワークに関連付けられている第１のユーザに対応する第１のノードと、
前記オンライン・ソーシャル・ネットワークに関連付けられているコンセプトまたは第２のユーザに各々対応する複数の第２のノードとを含む、工程と、
前記第１のユーザによって入力された非構造化テキスト・クエリを前記第１のユーザのクライアント・システムから受け取る工程と、
前記非構造化テキスト・クエリに基づき前記ソーシャル・グラフの１以上のエッジおよび１以上の第２のノードを識別する工程であって、識別された前記エッジおよび識別された前記第２のノードの各々は、前記非構造化テキスト・クエリの少なくとも一部に対応している、識別工程と、
複数の文法を有する文法フォレストを含むコンテキストフリー文法モデルにアクセスする工程であって、各文法は１以上の非終端トークンおよび１以上のクエリ・トークンを含み、前記文法フォレストは、複数の非終端トークンおよび複数のクエリ・トークンを含む順序付きツリーとして編成されており、各文法は、非終端トークンを通じて１以上の他の文法に隣接する、編成されたサブツリーである、工程と、
前記ソーシャル・グラフの識別された前記１以上のエッジおよび識別された前記１以上の第２のノードに基づき前記文法フォレストの１以上の文法における１以上のクエリ・トークンを識別する工程であって、識別された各クエリ・トークンは前記ソーシャル・グラフの識別された前記第２のノードまたは識別された前記エッジのうちの１以上に対応する、工程と、
前記文法フォレストの１以上の文法を選択する工程であって、選択された各文法は、前記ソーシャル・グラフの識別された前記エッジおよび識別された前記第２のノードの各々に対応する少なくとも１つのクエリ・トークンを含む、文法選択工程と、
１以上の構造化クエリを生成する工程であって、各構造化クエリは選択された文法に対応し、各構造化クエリは対応する前記選択された文法によって生成される自然言語文字列
に基づき、各構造化クエリは前記ソーシャル・グラフの識別された前記エッジおよび識別された前記第２のノードの各々に対応する少なくとも１つのクエリ・トークンを含む、構造化クエリ生成工程と、
前記クライアント・システムの前記第１のユーザに対し、前記第１のユーザによって入力された前記非構造化テキスト・クエリに応じて、前記第１のユーザに対する表示用に提案されるクエリとして前記構造化クエリのうちの１以上を送信する工程と、を実行するように構成されている、システム。