3

データベースにアナグラムフィールドを作成し、アルファベット順に格納された小文字の文字列を使用して、アナグラム作成アプリケーションを作成しました。

たとえば、吸引はcinostuになり、耳はaerになります。

私が今やりたいのは、検索した元のアナグラムからサブワードを作成することです。

例：「逮捕」、つまり「休息」と「凝視」の検索からサブセット単語を取得するにはどうすればよいでしょうか。

4

6 に答える 6

2

これは、アルファベット順にソートされた単語のリストを利用する、以前に使用したアプローチです。

1）あなたのターゲット単語を取り（逮捕）そしてそれを分類します（最初に）。

2）次に、ソートされた単語から、各文字が含まれるか除外される新しい文字列を生成します。N文字の単語の場合、これにより2**Nの可能な文字列が得られます。（私はPHPを知りませんが、必要に応じて擬似コードやPythonなどを提供できます。）

ターゲット単語には、a、e、r、r、s、t、st、rs、rt、rst、rr、rs、rt、rst、rrs、rrt、rrst、er、er、es、et、estがあります。 、ers、ert、erst、err、ers、ert、erst、errs、errt、errst、ae、ar、ar、as、at、ast、ars、art、arst、arr、ars、art、arst、arrs、arrt 、arrst、aer、aer、aes、aet、aest、aers、aert、aerst、aerr、aers、aert、aerst、aerrs、aerrt、aerrst

3）次に、これらの文字列をソート済みリストと照合します。ソートされたリストに表示されるものは、必要なサブセットの単語に対応しています。

たとえば、aerrstは完全なアナグラム（逮捕、最もまれ、ラスターなど）に対応し
ます。たとえば、aerstは並べ替えられたリスト（凝視、涙など）
に含まれます。たとえば、rrsは並べ替えられたリストには含まれません。

于 2009-07-03T10:41:12.797 に答える
1

元の単語の末尾にスペースを含めます。スペースが文字の途中で終わる各反復では、2つの単語を取得します。次に、これら2つの単語をテストできます。スペースが反復パターンの最初または最後にある場合は、それを切り取り、その1つの単語をテストします。

于 2009-07-02T13:22:28.953 に答える
1

これについてはまだ意味のあることは考えていませんが、申し訳ありませんが（やるべきことです！）、単語を生成することになりますが、これは母親の恋人のようにキャッシュされることを忘れないでください。誰かが検索するたびに飛ぶ。

CS。

于 2009-07-03T10:22:11.160 に答える
0

ちょっとボーク。あなたのコードをPHPに適応させようとしています、そして私は以下を持っています：

$ LetterCount = array（ "a" => 1、 "b" => 1、 "c" => 1、 "d" => 1、 "e" => 0、 "f" => 1、 "g" => 1、 "h" => 1、 "i" => 1、 "j" => 1、 "k" => 1、 "l" => 1、 "m" => 1、 "n" = > 1、 "o" => 1、 "p" => 1、 "q" => 1、 "r" => 1、 "s" => 1、 "t" => 1、 "u" => 1、 "v" => 1、 "w" => 1、 "x" => 1、 "y" => 1、 "z" => 1）;

$AsciiCodeLowerCaseA = 97;

for ($j = 1; $j < strlen($string); $j++) {
  $CurrentLetter = $string[$j];
  $AsciiCode = ord($CurrentLetter);
  $AlphabetPos = $AsciiCode - $AsciiCodeLowerCaseA + 1;
      $LetterCount[$AlphabetPos] = $LetterCount[$AlphabetPos] + 1;
}

時間を節約するために、配列宣言ビットをハードコーディングしました。

とにかく、それは機能していないようで、私にこのエラーを与えました：注意：未定義のオフセット：1

これが私が得ているエラーのスクリーンショットです。ループ内の各変数または配列にエコーを追加して、何が起こっているのかを理解できるかどうかを確認します。

http://i42.tinypic.com/11ryz4g.png

配列内のaplhabet文字を正しく識別していないため、配列の最後に誤って数字が追加されていると思います。

あなたが私が何をすべきだと思うか教えてください。

于 2009-07-03T10:02:50.597 に答える
0

このアプローチはあなたのアプローチとは少し異なりますが、プログラムで実装するのは簡単だと思います。パフォーマンスが最適かどうかはわかりませんが、お任せします:-)

まず、一致させたいすべての合法的な単語の辞書が必要です。

データベースに「辞書」または「単語」テーブルを作成します。最初の列には実際の単語が格納され、2番目の列にはすべて大文字または小文字に変換された単語が格納され、比較しやすくなります。次に、文字ごとに1つの整数列が表示されます。アルファベットAZ。

辞書ファイルをこのテーブルにインポートし、プログラムでアルファベットの各文字がこの単語に現れる回数を数え、この数をその文字の列に保存します。

単語の例：ブックキーパー

「bookkeeper」という単語を単語列に、1つを「b」、「p」、「r」列に、2つを「o」列と「k」列に、3つを「e」列に格納します。

辞書全体を文字数でインポートすると、次の方法を使用して、特定の単語に含まれる可能性のあるすべてのサブ単語をかなり簡単に判別できます。

  • 文字列の文字を数えます。
  • 特定の単語にない文字を使用しない、または単語に存在するよりも多くの特定の文字を含む、辞書テーブルからのすべての単語を返すSQLクエリを作成します。

これは、アルファベットを表す26の位置を持つメモリ内配列を作成することで実現できます。

例の単語：車両

SELECT Word FROM Dictionary WHERE NOT (
  (a >= 1) OR (b >= 1) OR (c >= 2) ... OR (z >= 1)
)

したがって、辞書内で「a」または「z」が含まれている単語は除外されます。これは、クエリによって「a」または「z」の数が少なくとも1である単語、および複数の「c」を使用する場合は除外されます。

26個の整数の配列を使用して、プログラムですべての「OR」条件を簡単に生成できます。すべて1から始まり、単語を調べて、見つかった各文字の適切な配列値に1を追加します。

UPDATE-最終カウントのサンプルコード

以下の私のコードサンプルを許してください-それはASP（VBScript）になります-しかし、あなたはPHPを把握して翻訳することができるはずです、そうでなければ親切な人にこれをしてもらいます。

Const AsciiCodeLowerCaseA = 97
InputWord = "Carrots"
LowerCaseInputWord = LCase(InputWord)

Dim LetterCount(26)

for i = 1 to 26
  LetterCount(i) = 1
next

for j = 1 to Len(InputWord)
  CurrentLetter = Mid(InputWord, j, 1)
  AsciiCode = Chr(CurrentLetter)
  AlphabetPos = AsciiCode - AsciiCodeLowerCaseA + 1
  LetterCount(AlphabetPos) = LetterCount(AlphabetPos) + 1
next

単語の各文字をASCII値に変換し、小文字の「a」のasciiコードを減算して1を加算すると、アルファベットのその文字の位置が1から26になります。ここで、その位置に1を加算します。配列。

直感に反しているように見えますが、配列内のすべての文字を1に初期化します。SQLステートメントを作成すると、入力した単語よりも文字数が多いすべての単語が削除されます。したがって、元の単語に文字が表示されない場合は、その文字が1つ以上ある単語を除外します。文字が1回表示される場合は、その文字が2つ以上ある単語を除外します。

于 2009-07-02T13:46:04.303 に答える
0

アンディ、

ASCIIコードを文字に変換し直す必要があると思います。文字で配列にインデックスを付けていますが、ASCII値で配列にアクセスしています。

少し変更したコードは次のとおりです。

$ LetterCount = array（ "a" => 1、 "b" => 1、 "c" => 1、 "d" => 1、 "e" => 0、 "f" => 1、 "g" => 1、 "h" => 1、 "i" => 1、 "j" => 1、 "k" => 1、 "l" => 1、 "m" => 1、 "n" = > 1、 "o" => 1、 "p" => 1、 "q" => 1、 "r" => 1、 "s" => 1、 "t" => 1、 "u" => 1、 "v" => 1、 "w" => 1、 "x" => 1、 "y" => 1、 "z" => 1）;

$AsciiCodeLowerCaseA = 97;

for ($j = **0**; $j < strlen($string); $j++) {
  $CurrentLetter = $string[$j];
  $AsciiCode = ord($CurrentLetter);
  $AlphabetPos = **chr($AsciiCode - $AsciiCodeLowerCaseA + 1);**
  $LetterCount[$AlphabetPos] = $LetterCount[$AlphabetPos] + 1;
}

また、文字列内の文字を1からインデックス付けしていることに気づきましたが、配列はゼロであります。

これももっと簡単かもしれないと思います（何かが足りない場合を除いて）

for($j = 0; $j < strlen($string); $j++) {
$LetterCount[$string[$j]]++;
}
于 2009-07-03T10:41:22.063 に答える