(57)【要約】【課題】与えられた文字列を並び替えて、自然さを考慮した他の文字列を生成すること。【解決手段】生成対象の文字列に含まれる複数の文字に関するデータである第１のデータを入力する入力手段と、前記第１のデータに基づいて、文字の並びの尤もらしさに関する条件が少なくとも含まれる所定の制約条件を満たす前記文字列に関するデータである第２のデータを生成する生成手段と、を有することを特徴とする。【選択図】図１
2020140627.tif 000002
【特許請求の範囲】
【請求項１】
生成対象の文字列に含まれる複数の文字に関するデータである第１のデータを入力する入力手段と、
前記第１のデータに基づいて、文字の並びの尤もらしさに関する条件が少なくとも含まれる所定の制約条件を満たす前記文字列に関するデータである第２のデータを生成する生成手段と、
を有することを特徴とする生成装置。
【請求項２】
前記生成手段は、
深さ優先探索アルゴリズムにより前記制約条件を満たす文字列を探索し、
前記深さ優先アルゴリズムでは、
前記文字列を構成する文字又は単語として、前記制約条件を満たさない文字又は単語が探索された場合、前記文字又は単語以降の文字又は単語の探索は行わない、ことを特徴とする請求項１に記載の生成装置。
【請求項３】
前記第１のデータが表す複数の文字に含まれる各文字の出現回数に基づいて、前記複数の文字に含まれる各文字の出現回数に関するデータを第１の出現回数データとし、
複数の単語データが記憶されている語彙記憶部を参照して、単語に含まれる各文字それぞれの出現回数が、前記第１の出現回数データが表す各文字それぞれの出現回数以下である単語の単語データを前記語彙記憶部から取得し、取得した各単語データそれぞれが表す単語に含まれる各文字の出現回数に関するデータを第２の出現回数データとして作成する手段を有し、
前記生成手段は、
前記第１の出現回数データと前記第２の出現回数データとを用いて、前記深さ優先探索アルゴリズムにより前記制約条件を満たす文字列を探索する、ことを特徴とする請求項２に記載の生成装置。
【請求項４】
前記尤もらしさに関する条件は、
所定の言語モデル又はルールベース手法によって算出される、文字の並びの尤もらしさを表す値に関する条件である、ことを特徴とする請求項１乃至３の何れか一項に記載の生成装置。
【請求項５】
前記制約条件には、
前記第２のデータが表す文字列を、前記第１のデータが表す複数の文字を並び替えた文字列とするための条件が含まれる、ことを特徴とする請求項１乃至４の何れか一項に記載の生成装置。
【請求項６】
前記第１のデータが表す複数の文字は、文、単語、句、節、単語の集合、文字と該文字の個数との組、のうちの少なくとも１つである、ことを特徴とする請求項１乃至５の何れか一項に記載の生成装置。
【請求項７】
生成対象の文字列に含まれる複数の文字に関するデータである第１のデータを入力する入力手順と、
前記第１のデータに基づいて、文字の並びの尤もらしさに関する条件が少なくとも含まれる所定の制約条件を満たす前記文字列に関するデータである第２のデータを生成する生成手順と、
を実行することを特徴とする生成方法。
【請求項８】
コンピュータを、請求項１乃至６の何れか一項に記載の生成装置における各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、生成装置、生成方法及びプログラムに関する。
【背景技術】
【０００２】
言葉遊びの一種としてアナグラムが知られている。アナグラムとは、与えられた文（又は、単語やフレーズ（句）等）に含まれる文字を並び替えて、別の文（又は、別の単語や別のフレーズ等）を作成することである。また、このように作成された別の文（又は、別の単語や別のフレーズ等）自体をアナグラムと言うこともある。例えば、「Trims cash」は「Christmas」のアナグラムである。
【０００３】
与えられた文（又は、単語やフレーズ等）からアナグラムを自動的に生成する技術が知られている（非特許文献１）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】"Internet anagram server", [online], <URL: https://wordsmith.org/anagram/>
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、アナグラムを生成する従来技術では、生成された文字列（アナグラム）の自然さを考慮するのが困難であった。すなわち、従来技術では、例えば、与えられた文字列に含まれる全ての文字を使った他の文字列を生成することはできるものの、人間が読んだ場合に意味がわからない文字列が生成されてしまうことがあった。
【０００６】
本発明は、上記の点に鑑みてなされたもので、与えられた文字列を並び替えて、自然さを考慮した他の文字列を生成することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するため、本発明の実施の形態における生成装置は、生成対象の文字列に含まれる複数の文字に関するデータである第１のデータを入力する入力手段と、前記第１のデータに基づいて、文字の並びの尤もらしさに関する条件が少なくとも含まれる所定の制約条件を満たす前記文字列に関するデータである第２のデータを生成する生成手段と、を有することを特徴とする。
【発明の効果】
【０００８】
与えられた文字列を並び替えて、自然さを考慮した他の文字列を生成することができる。
【図面の簡単な説明】
【０００９】
【図１】本発明の実施の形態における生成装置の機能構成の一例を示す図である。
【図２】本発明の実施の形態における生成装置のハードウェア構成の一例を示す図である。
【図３】本発明の実施の形態におけるアナグラム生成及び出力処理の一例を示すフローチャートである。
【図４】本発明の実施の形態における出現回数ベクトル及び行列の作成処理の一例を示すフローチャートである。
【図５】出現回数ベクトルF及び行列Xの一例を説明するための図である。
【図６】本発明の実施の形態における探索処理の一例を示すフローチャートである。
【発明を実施するための形態】
【００１０】
以下、本発明の実施の形態について説明する。本発明の実施の形態では、与えられた文字列を並び替えて、自然さを考慮した他の文字列を生成する生成装置１０について説明する。
【００１１】
ここで、生成装置１０に与えられる文字列としては、例えば文が挙げられるが、必ずしも文でなくてもよい。文字列としては、例えば、単語やフレーズ（句）、節であってもよいし、単語の集合であってもよい。又は、例えば、１つ以上の文字とこれら各文字の個数とが生成装置１０に与えられてもよい。以降では、一例として、生成装置１０に与えられる文字列は文であるものとし、この文に含まれる文字を並び替えて他の文（アナグラム）を生成する場合について説明する。
【００１２】
本発明の実施の形態における生成装置１０は、与えられた文に含まれる文字を並び替えた文（アナグラム）を深さ優先探索アルゴリズムにより探索しつつ、探索の途中で所定の言語モデルを用いて文の自然さに関する条件を評価する。そして、本発明の実施の形態における生成装置１０は、自然さに関する条件を満たさない文の探索を打ち切ることで（つまり、枝刈りを行うことで）、効率的に自然なアナグラムを生成する。
【００１３】
なお、上記の文の自然さに関する条件も含めて、与えられた文字列を並び替えて他の文字列を生成するために必要な条件を「制約条件」とも表す。したがって、本発明の実施の形態における生成装置１０が生成する文字列（例えば、アナグラム）は、「制約条件を満たす文字列」又は「制約条件を満たす並びの文字列」等ということができる。
【００１４】
＜生成装置１０の機能構成＞
まず、本発明の実施の形態における生成装置１０の機能構成について、図１を参照しながら説明する。図１は、本発明の実施の形態における生成装置１０の機能構成の一例を示す図である。
【００１５】
図１に示すように、本発明の実施の形態における生成装置１０は、機能部として、入力部１０１と、行列作成部１０２と、探索処理部１０３と、出力部１０４と、終了条件判定部１０５とを有する。また、本発明の実施の形態における生成装置１０は、記憶部として、語彙記憶部１０６と、言語モデル記憶部１０７とを有する。
【００１６】
語彙記憶部１０６は、アナグラムを生成する際に利用できる単語の集合を記憶している。
【００１７】
言語モデル記憶部１０７は、文の自然さを表す値を出力する言語モデルを記憶している。言語モデルとは、文を入力として、その文の次に来る単語の出現確率を出力するモデルのことである。
【００１８】
本発明の実施の形態では、言語モデルは、RNN（Recurrent Neural Network）で実現された言語モデル（以降、「RNN言語モデル」とも表す。）であるものとする。RNN言語モデルでは、任意のi個の単語w1, w2, ・・・, wi-1, wiに対する条件付き確率p(wi|w1, w2, ・・・, wi-1)を出力する。本発明の実施の形態では、この条件付き確率p(wi|w1, w2, ・・・, wi-1)を、単語w1, w2, ・・・, wi-1, wiで構成される文の自然さを表す値（つまり、文の尤もらしさを表す値）として用いる。このとき、条件付き確率p(wi|w1, w2, ・・・, wi-1)が、予め設定された所定の閾値以上である場合には、単語w1, w2, ・・・, wi-1, wiで構成される文は文の自然さに関する条件を満たすものとし、そうでない場合には、単語w1, w2, ・・・, wi-1, wiで構成される文は文の自然さに関する条件を満たさないものとする。
【００１９】
なお、i個の単語w1, w2, ・・・, wi-1, wiで構成される文の出現確率p(w1, w2, ・・・, wi-1, wi)を、この文の自然さを表す値として用いてもよい。この出現確率p(w1, w2, ・・・, wi-1, wi)は、p(w1, w2, ・・・, wi-1, wi)=p(w1)×p(w2|w1)×・・・×p(wi|w1, w2, ・・・, wi-1)と計算することができる。この場合、出現確率p(w1, w2, ・・・, wi-1, wi)が所定の閾値以上である場合には、単語w1, w2, ・・・, wi-1, wiで構成される文は文の自然さに関する条件を満たすものとし、そうでない場合には、単語w1, w2, ・・・, wi-1, wiで構成される文は文の自然さに関する条件を満たさないものとする。
【００２０】
ただし、本発明の実施の形態は、RNN言語モデル以外の言語モデルを用いることも可能である。単語や文字列、文等を入力として、これらの単語や文字列の並び、文自体等に対してその自然さを表す値（その尤もらしさを表す値）を出力する言語モデルであれば、任意の言語モデルを用いることができる。また、言語モデル以外にも、ルールベースの手法等によって、単語や文字列の並び、文の自然さを表す値が取得又は算出されてもよい。
【００２１】
入力部１０１は、入力データとして、文（以降、「入力文」とも表す。）を入力する。上述したように、入力部１０１は、入力データとして、単語や句、節、単語の集合、１つ以上の文字とこれら各文字の個数等が入力されてもよい。また、入力データは、音声認識技術等によって音声がテキスト化されたデータであってもよい。したがって、入力データは、生成装置１０が生成する文字列（例えば、アナグラム）に含まれる複数の文字に関するデータであればよい。
【００２２】
なお、入力部１０１は、任意の入力元から入力データを入力すればよい。例えば、入力部１０１は、補助記憶装置等に記憶されている入力データを入力してもよいし、通信ネットワークを介して接続された他の装置から送信された入力データを受信及び入力してもよいし、キーボード等の入力装置を用いてユーザにより入力された入力データを入力してもよい。
【００２３】
行列作成部１０２は、入力文に含まれる各文字の出現回数を表す出現回数ベクトルFを作成する。また、行列作成部１０２は、アナグラムに含まれる候補となる単語を語彙記憶部１０６から取得し、これら取得した単語に含まれる各文字の出現回数を行ベクトルとした行列Xを作成する。
【００２４】
探索処理部１０３は、出現回数ベクトルFと、行列Xと、言語モデル記憶部１０７に記憶されているRNN言語モデルとを用いて、深さ優先探索アルゴリズムにより、自然なアナグラム（つまり、入力データが表す文字列を並び替えた文字列であって、かつ、文の自然さに関する条件を満たす文字列）を探索及び生成する。なお、アナグラムが探索及び生成される度に、深さ優先探索アルゴリズムによってアナグラムを探索及び生成する処理（探索処理）は一度中断され、出力部１０４により、探索及び生成されたアナグラムが出力される。
【００２５】
出力部１０４は、出力データとして、探索処理部１０３により生成されたアナグラムを出力する。このとき、出力部１０４は、探索処理部１０３によりアナグラムが生成される度に、当該アナグラムを出力データとして出力する。すなわち、探索処理部１０３では一般に１つ以上のアナグラムが探索及び生成されるが、出力部１０４は、これら探索及び生成されたアナグラムを逐次的に出力データとして出力する。なお、入力データや語彙記憶部１０６に記憶されている単語等によっては、探索処理部１０３でアナグラムが１つも探索及び生成されないことも有り得る。
【００２６】
出力データは、入力データが表す文字列を並び替えた文字列であって、かつ、文の自然さに関する条件を満たす文字列であれば、文（アナグラム）に限られない。例えば、出力データとして、単語や句、節、単語の集合と各単語の並び順、１つ以上の文字とこれら各文字の個数及び並び順等であってもよい。
【００２７】
なお、出力部１０４は、任意の出力先に出力データを出力すればよい。例えば、出力部１０４は、補助記憶装置等に出力データを出力してもよいし、通信ネットワークを介して接続された他の装置に出力データを出力（送信）してもよいし、ディスプレイ等の表示装置に出力データを出力（表示）してもよい。
【００２８】
終了条件判定部１０５は、出力部１０４により出力データが出力された場合に、所定の終了条件を満たすか否かを判定する。終了条件判定部１０５により所定の終了条件を満たさないと判定された場合は、探索処理部１０３による探索処理が再開される。一方で、所定の終了条件を満たすと判定された場合は、探索処理は終了となる。ここで、所定の終了条件としては、例えば、出力部１０４により出力された出力データ数が所定の個数となったこと、入力データが表す文字列から全てのアナグラムが探索されたこと、等が挙げられる。
【００２９】
＜生成装置１０のハードウェア構成＞
次に、本発明の実施の形態における生成装置１０のハードウェア構成について、図２を参照しながら説明する。図２は、本発明の実施の形態における生成装置１０のハードウェア構成の一例を示す図である。
【００３０】
図２に示すように、本発明の実施の形態における生成装置１０は、ハードウェアとして、入力装置２０１と、表示装置２０２と、外部Ｉ／Ｆ２０３と、ＲＡＭ（Random Access Memory）２０４と、ＲＯＭ（Read Only Memory）２０５と、プロセッサ２０６と、通信Ｉ／Ｆ２０７と、補助記憶装置２０８とを有する。これら各ハードウェアは、それぞれがバス２０９を介して通信可能に接続されている。
【００３１】
入力装置２０１は、例えばキーボードやマウス、タッチパネル等であり、ユーザが各種操作を入力するのに用いられる。表示装置２０２は、例えばディスプレイ等であり、生成装置１０の処理結果（例えば、生成されたアナグラム等）を表示する。なお、生成装置１０は、入力装置２０１及び表示装置２０２の少なくとも一方を有していなくてもよい。
【００３２】
外部Ｉ／Ｆ２０３は、記録媒体２０３ａ等の外部記録媒体とのインタフェースである。生成装置１０は、外部Ｉ／Ｆ２０３を介して、記録媒体２０３ａの読み取りや書き込み等を行うことができる。記録媒体２０３ａには、生成装置１０が有する各機能部（例えば、入力部１０１、行列作成部１０２、探索処理部１０３、出力部１０４及び終了条件判定部１０５等）を実現する１以上のプログラム等が記録されていてもよい。
【００３３】
記録媒体２０３ａには、例えば、フレキシブルディスク、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disk）、ＳＤメモリカード（Secure Digital memory card）、ＵＳＢ（Universal Serial Bus）メモリカード等がある。
【００３４】
ＲＡＭ２０４は、プログラムやデータを一時保持する揮発性の半導体メモリである。ＲＯＭ２０５は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリである。ＲＯＭ２０５には、例えば、ＯＳ（Operating System）に関する設定情報や通信ネットワークに関する設定情報等が格納されている。
【００３５】
プロセッサ２０６は、例えばＣＰＵ（Central Processing Unit）やＧＰＵ（Graphics Processing Unit）等であり、ＲＯＭ２０５や補助記憶装置２０８等からプログラムやデータをＲＡＭ２０４上に読み出して処理を実行する演算装置である。生成装置１０が有する各機能部は、ＲＯＭ２０５や補助記憶装置２０８等に格納されている１以上のプログラムをＲＡＭ２０４上に読み出してプロセッサ２０６が処理を実行することで実現される。
【００３６】
通信Ｉ／Ｆ２０７は、生成装置１０を通信ネットワークに接続するためのインタフェースである。生成装置１０が有する各機能部を実現する１以上のプログラムは、通信Ｉ／Ｆ２０７を介して、所定のサーバ等から取得（ダウンロード）されてもよい。
【００３７】
補助記憶装置２０８は、例えばＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）等であり、プログラムやデータを格納している不揮発性の記憶装置である。補助記憶装置２０８に格納されているプログラムやデータには、例えば、ＯＳ、当該ＯＳ上で各種機能を実現するアプリケーションプログラム、生成装置１０が有する各機能部を実現する１以上のプログラム等がある。また、生成装置１０が有する各記憶部（例えば、語彙記憶部１０６や言語モデル記憶部１０７等）は、例えば補助記憶装置２０８を用いて実現可能である。ただし、これら各記憶部のうちの少なくとも１つの記憶部が、生成装置１０と通信ネットワークを介して接続される記憶装置等を用いて実現されていてもよい。
【００３８】
本発明の実施の形態における生成装置１０は、図２に示すハードウェア構成を有することにより、後述するアナグラム生成及び出力処理を実現することができる。なお、図２に示す例では、本発明の実施の形態における生成装置１０が１台の装置（コンピュータ）で実現されている場合を示したが、これに限られない。本発明の実施の形態における生成装置１０は、複数台の装置（コンピュータ）で実現されていてもよい。また、１台の装置（コンピュータ）には、複数のプロセッサ２０６や複数のメモリ（ＲＡＭ２０４やＲＯＭ２０５、補助記憶装置２０８等）が含まれていてもよい。
【００３９】
＜アナグラム生成及び出力処理＞
次に、本発明の実施の形態における生成装置１０がアナグラムを生成及び出力する処理について、図３を参照しながら説明する。図３は、本発明の実施の形態におけるアナグラム生成及び出力処理の一例を示すフローチャートである。
【００４０】
まず、入力部１０１は、入力データとして、入力文を入力する（ステップＳ１０１）。
【００４１】
次に、行列作成部１０２は、出現回数ベクトルF及び行列Xを作成する（ステップＳ１０２）。なお、出現回数ベクトルF及び行列Xの作成処理の詳細については後述する。
【００４２】
次に、探索処理部１０３は、出力部１０４により出力データとして出力される文Sを空文（例えば、S=""）に初期化する（ステップＳ１０３）。後述する探索処理において、Sに対して単語が追加されることで、出力データとして出力される文（つまり、例えばアナグラム）が生成される。
【００４３】
次に、探索処理部１０３は、出現回数ベクトルFと、行列Xと、言語モデル記憶部１０７に記憶されているRNN言語モデルとを用いて、深さ優先探索アルゴリズムにより、制約条件を満たすアナグラムを探索及び生成する（ステップＳ１０４）。ここで、探索処理は、出現回数ベクトルFと行列Xと文Sとを引数とする関数SEARCH(F, X, S)が呼び出されることで実行されるものとする。なお、探索処理の詳細については後述する。
【００４４】
探索処理で制約条件を満たすアナグラムが探索及び生成された場合、探索処理は一度中断される（後述するステップＳ３１５）。そして、出力部１０４は、出力データとして、探索処理部１０３により生成されたアナグラム（つまり、文S）を、例えばディスプレイ等の表示装置２０２に出力する（ステップＳ１０５）。これにより、探索処理で制約条件を満たすアナグラムが探索及び生成される度に、逐次的に、当該アナグラムが表示装置２０２に表示される。なお、制約条件を満たすアナグラム（S）は、探索処理の解として得られる。
【００４５】
次に、終了条件判定部１０５は、所定の終了条件を満たすか否かを判定する（ステップＳ１０６）。
【００４６】
ステップＳ１０６で所定の終了条件を満たすと判定された場合、生成装置１０は、アナグラム生成及び出力処理を終了する。
【００４７】
一方で、ステップＳ１０６で所定の終了条件を満たさないと判定された場合、探索処理部１０３は、探索処理の実行を再開する（ステップＳ１０７）。すなわち、探索処理部１０３は、制約条件を満たすアナグラムが探索及び生成されたことによって中断されていた探索処理の実行を再開する。なお、探索処理の実行を再開する際には、探索処理を中断した位置（後述するステップＳ３１５）の次の処理から当該探索処理の実行を再開する。
【００４８】
このように、図３に示すアナグラム生成及び出力処理では、探索処理で制約条件を満たすアナグラムが探索及び生成される度に、逐次的に、当該アナグラムを出力データとして出力し、探索処理を継続（再開）するか否かを判定する。ただし、必ずしも逐次的に出力データを出力する必要はなく、例えば、探索処理で制約条件を満たす全てのアナグラムを探索及び生成した後、これら生成されたアナグラムを出力データとして出力してもよい。
【００４９】
《出現回数ベクトルF及び行列Fの作成処理》
次に、上記のステップＳ１０２における出現回数ベクトルF及び行列Xを作成する処理について、図４を参照しながら説明する。図４は、本発明の実施の形態における出現回数ベクトル及び行列の作成処理の一例を示すフローチャートである。
【００５０】
まず、行列作成部１０２は、入力文に含まれる各文字の出現回数を表す出現回数ベクトルFを作成する（ステップＳ２０１）。なお、出現回数は、「出現頻度」又は単に「頻度」等と称されてもよい。
【００５１】
ここで、一例として、入力文が「Christmas」である場合の出現回数ベクトルFを図５に示す。入力文が「Christmas」である場合、文字「c」の入力文中における出現回数は1回、文字「h」の入力文中における出現回数は1回、文字「r」の入力文中における出現回数は1回、文字「i」の入力文中における出現回数は1回、文字「s」の入力文中における出現回数は2回、文字「t」の入力文中における出現回数は1回、文字「m」の入力文中における出現回数は1回、文字「a」の入力文中における出現回数は1回である。
【００５２】
したがって、例えば、アルファベット順に各文字の出現回数を並べることで、図５に示す出現回数ベクトルF=(1, 1, 1, 1, 1, 1, 2, 1)が得られる。なお、図５に示す出現回数ベクトルFでは、１次元目が文字「a」、２次元目が文字「c」、３次元目が文字「h」、４次元目が文字「i」、５次元目が文字「m」、６次元目が文字「r」、７次元目が文字「s」、８次元目が文字「t」にそれぞれ対応している。
【００５３】
このように、出現回数ベクトルFは、入力文中の異なる文字の種類数を次元数、各要素を対応する文字の入力文中における出現回数とするベクトルで表される。
【００５４】
次に、行列作成部１０２は、入力文に含まれる文字で構成される単語であって、単語を構成する各文字の出現回数が、入力文中の当該文字の出現回数以下である単語を語彙記憶部１０６から取得する（ステップＳ２０２）。例えば、入力文が「Christmas」である場合、文字「c」、「h」、「r」、「i」、「s」、「t」、「m」及び「a」のうちの少なくとも１つの文字で構成される単語であって、当該単語を構成する各文字の出現回数が、入力文中の当該文字の出現回数以下である単語が取得される。このような単語としては、例えば、「trims」、「a」、「cash」、「shirts」、「has」等が挙げられる。以降では、一例として、単語「trims」、「a」、「cash」、「shirts」及び「has」が取得されたものとして説明を続ける。
【００５５】
次に、行列作成部１０２は、上記のステップＳ２０２で取得した各単語中の各文字の出現回数を行ベクトルとした行列Xを作成する（ステップＳ２０３）。このとき、各行ベクトルの次元数は出現回数ベクトルFと同一とし、かつ、各要素と各文字との対応関係も出現回数ベクトルFと同一とする。なお、単語中に含まれない文字に対応する要素の値（出現回数）は「0」とする。
【００５６】
例えば、単語「trims」の場合、この単語の行ベクトルは(0, 0, 0, 1, 1, 1, 1, 1)となる。同様に、例えば、単語「a」の場合、この単語の行ベクトルは(1, 0, 0, 0, 0, 0, 0, 0)となる。以降も同様に、単語「cash」の行ベクトルは(1, 1, 1, 0, 0, 0, 1, 0)、単語「shirts」の行ベクトルは(0, 0, 1, 1, 0, 1, 2, 1)、単語「has」の行ベクトルは(1, 0, 1, 0, 0, 0, 1, 0)となる。これにより、図５に示す行列Xが作成される。なお、図５に示す行列Xでは、上から順に、単語「trims」の行ベクトル、単語「a」の行ベクトル、単語「cash」の行ベクトル、単語「shirts」の行ベクトル及び単語「has」の行ベクトルをそれぞれ並べたが、この順は任意の順でよい。
【００５７】
このように、行列Xは、アナグラムを構成する単語の候補をそれぞれ各行とし、これら単語の候補に含まれる各文字の出現回数を各要素とする行ベクトルで構成される。
【００５８】
《探索処理》
次に、上記のステップＳ１０４及びステップＳ１０７における探索処理について、図６を参照しながら説明する。図６は、本発明の実施の形態における探索処理の一例を示すフローチャートである。なお、探索処理は、出現回数ベクトルFと行列Xと文Sとを引数とする関数SEARCH(F, X, S)が呼び出されることで実行される。
【００５９】
まず、探索処理部１０３は、行列Xの列の数が0であるか否かを判定する（ステップＳ３０１）。なお、後述するステップＳ３１１では、既に文Sに使用され、これ以上使用できない文字に対応する列が行列Xから削除される。
【００６０】
ステップＳ３０１で行列Xの列の数が0でないと判定された場合、探索処理部１０３は、集合Mを空集合に初期化する（ステップＳ３０２）。集合Mは、同一の文Sを引数としたSEARCH(F, X, S)が複数回呼び出されることを防止するためのキャッシュである。
【００６１】
次に、探索処理部１０３は、出現回数ベクトルFで値が１以上の要素（つまり、文字の出現回数が１以上である要素）に対応する列cであって、後述するステップＳ３０４で未だ選択されていない列cが行列Xにあるか否かを判定する（ステップＳ３０３）。
【００６２】
ステップＳ３０３で該当の列cが行列Xにないと判定された場合、探索処理部１０３は、探索処理を終了する。この場合、生成装置１０は、当該探索処理の呼び出し元の位置（ステップＳ１０４、ステップＳ１０７、又は後述するステップＳ３１２のいずれか）の次の処理を実行する。
【００６３】
一方で、ステップＳ３０３で該当の列cがあると判定された場合、探索処理部１０３は、出現回数ベクトルFで値が１以上の要素に対応する列cであって、未だ選択していない列cを行列Xから選択する（ステップＳ３０４）。以降では、本ステップで選択された或る列cを「選択列c」と表す。
【００６４】
次に、探索処理部１０３は、選択列cで値が１以上の要素であって、後述するステップＳ３０６で未だ選択されていない行rに対応する要素が選択列cにあるか否かを判定する（ステップＳ３０５）。
【００６５】
ステップＳ３０５で該当の要素が選択列cにないと判定された場合、探索処理部１０３は、ステップＳ３０３に戻る。これにより、上記のステップＳ３０３では、出現回数ベクトルFで値が１以上の要素に対応する列cであって、未だ選択されていない列cが行列Xにあるか否かが判定される。
【００６６】
一方で、ステップＳ３０５で該当の要素が選択列cにあると判定された場合、探索処理部１０３は、選択列cで値が１以上の要素に対応する行rであって、未だ選択していない行rを行列Xから選択すると共に、この選択した行rに対応する単語wrを選択する（ステップＳ３０６）。以降では、本ステップで選択された或る行rを「選択行r」、この選択行rに対応する単語wrを「選択単語wr」と表す。なお、選択単語wrは、語彙記憶部１０６が選択されればよい。
【００６７】
次に、探索処理部１０３は、選択単語wrが以下の制約条件１〜制約条件３を全て満たすか否かを判定する（ステップＳ３０７）。なお、以下の制約条件１が文の自然さに関する条件に該当する。一方で、制約条件２はアナグラムを探索及び生成するための条件、制約条件３はその探索を効率的に行うための条件である。
【００６８】
制約条件１：言語モデル記憶部１０７に記憶されているRNN言語モデルを用いて条件付き確率p(wr|S)を出力した上で、この条件付き確率p(wr|S)が所定の閾値以上であるか否か
条件付き確率p(wr|S)が所定の閾値以上である場合は制約条件１を満たし、そうでない場合は制約条件１を満たさない。
【００６９】
制約条件２：選択単語wrに含まれる各文字の出現回数が、出現頻度ベクトルFで当該文字に対応する要素の値以下である否か
選択単語wrに含まれる全ての文字の出現回数が、出現頻度ベクトルFでこれら全ての文字にそれぞれ対応する要素の値以下である場合は制約条件２を満たし、そうでない場合は制約条件２を満たさない。
【００７０】
制約条件３：選択単語wrが集合Mに含まれていないか否か
選択単語wrが集合Mに含まれていない場合は制約条件３を満たし、そうでない場合は制約条件３を満たさない。
【００７１】
ステップＳ３０７で制約条件１〜制約条件３のうちの少なくとも１つの制約条件を満たさないと判定された場合、探索処理部１０３は、ステップＳ３０５に戻る。これにより、上記のステップＳ３０５では、選択列cで値が１以上の要素であって、未だ選択されていない行rに対応する要素が選択列cにあるか否かが判定される。このように、制約条件１〜制約条件３のうちの少なくとも１つの制約条件を満たさない場合は、深さ優先探索アルゴリズムにおける枝刈りが行われ、効率的にアナグラムを探索及び生成することが可能となる。
【００７２】
一方で、ステップＳ３０７で制約条件１〜制約条件３の全てを満たすと判定された場合、探索処理部１０３は、文Sの末尾に選択単語wrを追加した文S´を作成する（ステップＳ３０８）。
【００７３】
次に、探索処理部１０３は、集合Mに選択単語wrを追加する（ステップＳ３０９）。
【００７４】
次に、探索処理部１０３は、行列Xから選択行rを削除すると共に、選択単語wrに含まれる各文字の出現回数を、出現回数ベクトルFの当該文字の要素から減算する（ステップＳ３１０）。例えば、選択単語wrが「shirts」である場合、探索処理部１０３は、図５に示す出現回数ベクトルFの各要素のうち、３次元目の要素と４次元目の要素と６次元目の要素と８次元の要素とからそれぞれ１を減算すると共に、７次元目の要素から２を減算する。以降では、本ステップで選択行rが削除された後の行列Xを「行列X´」と表し、減算後の出現回数ベクトルFを「出現回数ベクトルF´」と表す。
【００７５】
次に、探索処理部１０３は、出現回数ベクトルF´で値が0の要素に対応する列c´と、この列c´で値が１以上の要素に対応する行r´とを行列X´から削除する（ステップＳ３１１）。これにより、選択単語wrが文Sに追加された結果、使用できなくなった文字に対応する列c´と、当該文字が含まれる単語に対応する行r´とが行列X´から削除される。以降では、この削除後の行列X´を「行列X´´」と表す。
【００７６】
次に、探索処理部１０３は、F=F´、X=X´´、S=S´として関数SEARCH(F, X, S)を呼び出して、探索処理を実行する（ステップＳ３１２）。すなわち、探索処理部１０３は、探索処理を再帰的に実行する。
【００７７】
次に、探索処理部１０３は、上記のステップＳ３１２で実行された探索処理の終了後、バックトラック処理として以下の（１）〜（３）を実行する（ステップＳ３１３）。
【００７８】
（１）上記のステップＳ３０８でSに追加された選択単語wrを削除して、S´をSに戻す。
【００７９】
（２）上記のステップＳ３１０で削除された選択行rと、上記のステップＳ３１１で削除された列c´及び行r´とを行列X´´に追加して、行列X´´を行列Xに戻す。
【００８０】
（３）上記のステップＳ３１０で減算された値を出現回数ベクトルF´に加算して、出現回数ベクトルF´を出現回数ベクトルFに戻す。
【００８１】
これにより、深さ優先探索アルゴリズムにおけるバックトラック（又は、バックトラッキング）が行われる。
【００８２】
一方で、上記のステップＳ３０１で行列Xの列の数が0であると判定された場合、探索処理部１０３は、Sをメモリやファイル等に出力する（ステップＳ３１４）。すなわち、探索処理部１０３は、関数SEARCH(F, X, S)の戻り値としてSを出力する。ここで出力されたSが探索処理の解（より正確には、解の１つ）であり、上記のステップＳ１０５で出力部１０４により出力される。
【００８３】
次に、探索処理部１０３は、探索処理の実行を中断する（ステップＳ３１５）。そして、生成装置１０は、上記のステップＳ１０５の処理に進む。なお、上記のステップＳ１０７で探索処理の実行を再開可能とするため、探索処理部１０３は、再開に必要な情報（例えば、現時点の出現回数ベクトルFや行列X、文S、探索処理の再開位置等）をメモリ等に格納した上で探索処理の実行を中断する。
【００８４】
＜まとめ＞
以上により、本発明の実施の形態における生成装置１０では、与えられた文字列を用いて、深さ優先探索アルゴリズムにより、制約条件を満たす他の文字列（例えば、文として自然なアナグラム等）を生成することが可能となる。また、このとき、本発明の実施の形態における生成装置１０では、他の文字列を構成する単語が制約条件を満たさない場合には、深さ優先探索アルゴリズムの枝刈りを行うことで、効率的に制約条件を満たす他の文字列を生成することが可能となる。
【００８５】
なお、本発明の実施の形態では、一例として、深さ優先探索アルゴリズムにより、制約条件を満たす全てのアナグラムを解として探索及び生成する場合について説明したが、例えば、制約条件を満たす任意の個数のアナグラム（特に、制約条件を満たす１つのアナグラムも含む）を解として探索及び生成されてもよい。この場合、生成装置１０は、予め設定された個数のアナグラムが解として探索及び生成された場合に、探索処理を打ち切ればよい。
【００８６】
本発明は、具体的に開示された上記の実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【符号の説明】
【００８７】
１０        生成装置
１０１      入力部
１０２      行列作成部
１０３      探索処理部
１０４      出力部
１０５      終了条件判定部
１０６      語彙記憶部
１０７      言語モデル記憶部
【図１】
2020140627.tif 000003
【図２】
2020140627.tif 000004
【図３】
2020140627.tif 000005
【図４】
2020140627.tif 000006
【図５】
2020140627.tif 000007
【図６】
2020140627.tif 000008