E. Ya。Geekの著書「 Entertaining Mathematical Games 」の著書で有名な著者は、そのような16通りのソリューション、ハエから象を作る方法、fly-mura-tour-tara-kara-kare-kare-kafr-kayur-を出版しました。 kayuk-hook-apricot-lesson-term-stock-groan-elephant。
それで、ある日、私はプログラムでこのタスクに取り組む機会がありました。
象のハエから、最初のバージョン
正直なところ、ハエのゾウは非常に迅速に処理されることがわかりました。
ソリューションの一般的な考え方：
-名詞の辞書を取る
-最後の単語を達成できる場合は、ソースワードから最後の単語まで反復アルゴリズムを実行します。
-結果のチェーンを発行し、彼女は最小の長さのために努力することが望ましい
だから...
1）名詞の辞書
最初の段落でも問題があることがわかりました-名詞の価値のある辞書を見つけることは別のサブタスクであることが判明しました。 どこか正確には覚えていませんが、耐えられる既製の辞書を見つけました。 1行に1ワード、utf8、区切り文字\ r \ nの形式-将来的に残されます。
2）アルゴリズム
当然、彼はハエとゾウがこの問題を解決したかどうか、そしてどのように解決したかを尋ねました。 ここでplanetcalc.ru/544に良い解決策が見つかりました。 javascriptの下の4語のみの単語の場合（これは実際にはこのアプリケーションの正しい考えです。ブラウザでクライアントハードウェアを検索できる場合、サーバーの容量を増やすことは意味がありません）。 ただし、ソースコードは調べませんでしたが、記事の後半で正しい推論を調べました。
実際、すべてのオプションを使用してツリー構造をアルゴリズムとして使用し、検索語が見つかるまで次のレベルを設定する場合、十分なリソースはありません。
たとえば、単語CORAには、「山」から「裁判所」へと思い浮かぶ一般的な単語から19の遷移があります。
5（合計！）の平均修正数について非常に楽観的な推定値を与えたとしても、ある単語について最小パスが10ステップである場合、メモリツリーは5 10〜 = 1000万ノードに収まるはずです。 ツリーの構造を維持するオーバーヘッド（祖先からの子孫への少なくとも2つのポインター、それぞれ4/8バイト）とノードデータ（変数の言語/構造ラッパー+データ自体：utf8の行文字は10バイト以上）を保存するオーバーヘッドを考えるとこのような条件のRAM要件は、少なくとも約200〜300 MBです。 また、状況はさらに悪化する可能性があります。
遺伝的アルゴリズムが選択されました。
さらに、彼はここで単に頼みます-単語の文字の変更は本質的に突然変異です。 「出産」中の子孫の生存の条件は、辞書にあることです。 競争の成功の条件であるフィットネスは、希望する単語との類似度です。
単語遷移連鎖の遺伝的検索の機能
/** * * * * * @param string $wordFrom - * @param string $wordTo - * @return array * @throws WordWizardException */ public function FindMutationChain($wordFrom, $wordTo, $maxSteps = 1000, $maxPopulation = 100) { $resultKeysChain = []; $resultChain = []; // $wordFrom = mb_convert_case($wordFrom, MB_CASE_LOWER); $wordTo = mb_convert_case($wordTo, MB_CASE_LOWER); $fromLen = mb_strlen($wordFrom); $toLen = mb_strlen($wordTo); // if ($fromLen != $toLen) { throw new WordWizardException(" ."); } // $wordFromKey = binary_search($this->_dictionary, $wordFrom); // , , $wordToKey = binary_search($this->_dictionary, $wordTo); if ($wordToKey < 0) { throw new WordWizardException(" \"$wordTo\" ."); } // $mutationChains = [ [ 'keys' => [$wordFromKey], 'mutatedPositions' => [-1] ] ]; $population = 1; // for ($step = 0; $step < $maxSteps; $step++) { // ? foreach ($mutationChains as $mutationChain) { if (end($mutationChain['keys']) == $wordToKey) { // ( ) $resultKeysChain = $mutationChain['keys']; break 2; } } // $newMutationChains = []; foreach ($mutationChains as $mutationChain) { $lastKey = end($mutationChain['keys']); $lastMutatedPos = end($mutationChain['mutatedPositions']); $lastWord = $this->_dictionary[$lastKey]; $nextMutations = $this->FindMutationVariants($lastWord, $wordTo, $fromLen, $lastMutatedPos, $mutationChain['keys']); foreach ($nextMutations as $mutation) { list($nextKey, $nextMutatedPos) = $mutation; $nextWord = $this->_dictionary[$nextKey]; $score = $this->GetWordScore($nextWord, $wordTo); // $newMutationChain = $mutationChain; $newMutationChain['keys'][] = $nextKey; $newMutationChain['mutatedPositions'][] = $nextMutatedPos; $newMutationChain['score'] = $score; $newMutationChains[] = $newMutationChain; } } // $mutationChains = $newMutationChains; // .. if (empty($mutationChains)) { throw new WordWizardException(" $step ( $maxSteps) . ."); } // " " ( ) usort($mutationChains, function($a, $b) { return $b['score'] - $a['score']; }); // - array_splice($mutationChains, $maxPopulation); } // ? if ($step == $maxSteps) { throw new WordWizardException(" ($maxSteps), ."); } // if ($resultKeysChain) { foreach ($resultKeysChain as $key) { $resultChain[] = $this->_dictionary[$key]; } } return $resultChain; }
正直に同じplanetcalc.ru/544の説明から重み関数を取りました。 私はそれがなぜであるか考えました、私自身はこれを理解しました
-正しい位置にある文字の正体3ポイント：コメントなし、ここでの最大スコアは論理的です
-別の位置ではあるが、母音は2ポイント：母音を正しい場所にドラッグすることははるかに困難ですが、子音の変異と混同しやすくなり、そのようなオプションが右の母音に追加されます。 さらに、母音は「調子を整えます」-検索された単語に必要な子音を含む子音は、回りやすくなります。
-一般的な1点の母音の存在：上記と同様の理由で、母音を変化させることは子音よりもはるかに困難です。
それとは別に、検索の全体の段階で、最終的には一定の比較が行われるはずの参照語が同一であることに注意してください。 たとえば、同じ象 。 したがって、「象を比較するために断片に分解する」（貧弱な動物）は、この解剖学的形態とキャッシュでは論理的です。
簡単にするために、また考え直さずに、評価関数に最も単純なキャッシュを直接構築しました。
単語のペアのマッチング関数
/** * * * @param string $word - * @param string $comparationWord - * @return int */ public function GetWordScore($word, $comparationWord) { // - , - static $cachedComparationWord = ''; static $wordLen = 0; static $cwLetters = []; if ($cachedComparationWord != $comparationWord) { $cachedComparationWord = $comparationWord; $wordLen = mb_strlen($comparationWord); $cwLetters = []; for ($i = 0; $i < $wordLen; $i++) { $letter = mb_substr($comparationWord, $i, 1); $cwLetters[$i] = [ 'letter' => $letter, 'isVovel' => false === mb_strpos($this->_vovels, $letter) ? false : true, ]; } } $score = 0; for ($i = 0; $i < $wordLen; $i++) { $letter = mb_substr($word, $i, 1); // = 3 if ($letter == $cwLetters[$i]['letter']) { $score += 3; continue; } $isVovel = (false === mb_strpos($this->_vovels, $letter) ? false : true); if ($isVovel) { if ($cwLetters[$i]['isVovel']) { // = 2 $score += 2; } else { // = 1 $score += 1; } } } return $score; }
突然変異の新しいバリアントの検索は、指定された単語から始まる辞書と辞書を通過します。 いくつかの追加の論理的な制限があります。
最初の制限は、変異の文字の許容位置です。 実際、たとえば、最後のステップで3文字目を変更して「muKha」-「muZa」を移動した場合、次のステップで「muZa」-「muRa」という突然変異は意味がありません。 結局のところ、可能な限り短いチェーンに興味があります。 そして、あなたはすぐに「muHa」-「muRa」に移動できるので、意図的に不必要なステップを踏んでいることがわかります。 したがって、関数のパラメーターの1つは、最後の突然変異の位置です。
2番目の制限は、チェーン内の単語の一意性です。 説明も簡単です。 「ハエ」-「 小麦粉 」-「ブナ」-「ボラックス」-「ムラ」-「 小麦粉 」-「手」というチェーンがあるとします。 明らかに、「 小麦粉 」-「ブナ」-「ホウ砂」-「ムーア」の部分は、チェーン内では不要でした。 そして、たとえ最終的な「象」に到達したとしても、まったく同じですが、繰り返された一意の単語のチェーンは短くなります。 そしてそれは良いです。 したがって、繰り返しのためにこのようなサイクルは必要ありません。 したがって、チェーンですでに使用されている単語の配列（この場合は単語のID）を、変異バリアントを検索するための関数のもう1つのパラメーターにします。
語長パラメーターは、mb_strlenの一致で保存したものです。 そのため、この方法は個人的に考案されましたが、試験やテストでは公開されていました。 そのようなものを本番環境に入れないでください:)いずれにしても、チェックをカバーせずに。
そして最後の言葉は...多分ある種の人間の反省、あるいは多分直観-後で使用する可能性を残しました。 それでも、子孫のセットを取得する機能から、彼らがどのように見えるべきかに何らかの依存を期待することは論理的です。 ここで一次スクリーニングを妨げるものは何もありません。 しかし、今のところ-使用されていません。
可能な突然変異を取得するための機能
/** * {id , } * * * * @param string $wordFrom - * @param string $wordTo - * @param int $wordLen - * @param int $disabledMutationPos - , ( ) * @param array $excludedWordKeys - * @return array */ public function FindMutationVariants($wordFrom, $wordTo, $wordLen, $disabledMutationPos, $excludedWordKeys) { $variants = []; for ($mutPos = 0; $mutPos < $wordLen; $mutPos++) { // ( , . ) if ($mutPos == $disabledMutationPos) continue; // $mutPos- $wordBeginning = mb_substr($wordFrom, 0, $mutPos); $wordEnding = mb_substr($wordFrom, $mutPos + 1); // if ($mutPos < self::SUB_DICTIONARIES_MAX) { // , $subDictionary = $this->_subDictionaries[$mutPos + 1]; $pseudoWord = $wordBeginning . $wordEnding; $pseudoWordKey = binary_search($subDictionary, $pseudoWord, 0, NULL, [$this, 'SubDictionaryWordsCmp']); if ($pseudoWordKey >= 0) { // PHP , // $row = $subDictionary[$pseudoWordKey]; foreach ($row[self::_SDW_WORDS_KEYS] as $key) { // - if (in_array($key, $excludedWordKeys)) continue; $variants[$key] = [$key, $mutPos]; } } } else { // - , if ($mutPos == 0) { // , // , - // ( ) $key = 0; } else { // $key = binary_search($this->_dictionary, $wordBeginning); if ($key < 0) { $key = -$key; } } // for ($key; isset($this->_dictionary[$key]); $key++) { $word = $this->_dictionary[$key]; // , if (mb_substr($word, 0, $mutPos) != $wordBeginning) { break; } // ( ) if (mb_strlen($word) != $wordLen) { continue; } // , if (mb_substr($word, $mutPos + 1) != $wordEnding) { continue; } // - if (in_array($key, $excludedWordKeys)) continue; // , $variants[$key] = [$key, $mutPos]; } } } return $variants; }
3）辞書を操作する
アルゴリズムは優れていますが、ファイル（データ）のソースがファイルの形式であり、検索アルゴリズムから効率的に多くの作業を行う必要があります。
はい、この辞書ファイルはアルファベット順にソートされています。 そして、それほど巨大ではなく、約1 MBしかないので、RAM全体で動作するように安全にダウンロードできます。
この場合、もちろん、言語に応じて配列の形式でデータ構造に「ロードおよびレイアウト」する場合、辞書はより多くのメモリを消費することを理解する必要があります。 PHP 5.4の場合、ダウンロードした形式の辞書の重量は約6 MBであることが判明しました。
ここにも。
将来を見据えて、辞書はさらに重くなります。
[データベースの論理的な使用についての最初の考えがここにあります。 しかし、私は彼女なしで最初にそれをしようとすることに決めました。]
ただし：
-PHPではarray_searchはダムソートツールであり、「ちょっと、配列がソートされ、バイナリを探します」という可能性はありません。他に適切な機能はありません。フリップキーを使って松葉杖をプレイしたくはありませんでした。
-ソートされた配列にクイックバイナリ検索機能があったとしても、エンボス文字を含むマスクで検索する問題があります。
3.1）一意でない値の最初のソートされた配列でのクイック検索
最初の問題は、PHP用のバイナリ検索バイクによって解決されます。 私は友人から乗車を借りました、 terenceyim.wordpress.com/2011/02/01/all-purpose-binary-search-in-php 。
このバージョンのバイナリ検索は、最も一般的な算術演算であり、連続した整数番号（たとえば、0〜N-1のキー）でソートされた配列での作業に適していることに注意してください。
私は真実をそのままではなく、検索を修正しました。 一意でない要素の配列の場合、picikは最初に見つかった等しい検索で停止しました。 そして、配列の同じ要素からキーで最初の位置を与える必要がありました。 重要なのは、後続のアルゴリズムを単純化できるようにすることです。また、等しいセットを反復処理する場合は、配列の下のキーをたどるだけです。
例：MUAを探しています。アレイがあります（以下を参照）[... 99-MS（t）ITEL、100-MU（s）A、101-MU（k）A、102-MU（p）A、103-MU（ r）A、104-MU（x）A、105-MU（r）AVEY、106-MU（p）AVEYNIK ...]通常のバイナリ検索は、次の反復でヒットします。たとえば、キー102に入ります。要素の値（MUA、単語MURAから来ました） ）は希望するものと等しく（MUA、MUHAの子孫を探しています）、このキーは私たちに届きます。 そして、バストアップとバストダウンでロジックを乱雑にします。 変更されたアルゴリズムは、最初のキーであるキー100を検出します。その後、==要素が検索されるまで、配列を順次下に移動できます。
変更されたバイナリ検索
/** * * * @param array $a - ( ) * @param mixed $needle - , * @param int $first - () * @param int $last - ( ) * @param string $compare - . usort * * @return int * . * -(insert_index + 1). * insert_index , * , sizeof($a) * . */ function binary_search(array $a, $needle, $first = 0, $last = NULL, $compare = 'default_cmp') { if ($last === NULL) { $last = count($a); } $lo = $first; $hi = $last - 1; while ($lo <= $hi) { $mid = (int)(($hi - $lo) / 2) + $lo; $cmp = call_user_func($compare, $a[$mid], $needle); if ($cmp < 0) { $lo = $mid + 1; } elseif ($cmp > 0) { $hi = $mid - 1; } else { $hi = $mid - 1; // $mid // , . //return $mid; } } $cmp = call_user_func($compare, $a[$lo], $needle); return $cmp == 0 ? $lo : -($lo + 1); } /** * * * @param mixed $a - * @param mixed $b - * @return int : -1 , 0 , 1 */ function default_cmp($a, $b) { return ($a < $b) ? -1 : (($a > $b) ? 1 : 0); }
3.2）補助疑似単語辞書
2番目-私は「RAMがそれをかなり耐えるだろう」と考え、辞書を通してそれをすることにしました。 i番目の辞書がメイン辞書から作成され、単語からi番目の文字が切り取られます。 MACHINE =>（i = 2）MACHINEと入力します。 そのような辞書の場合、辞書がある位置で文字がノックアウトされた場合に同じバイナリ検索を使用できます。
エンボス文字が単語の先頭から離れすぎており、この位置にサブ辞書がない場合、次のように進みます。
-メイン辞書で「途切れない始まり」を探しています
-見つかった位置から、検索しながら要素（単語）が始まり、必要な長さを持ち、これらの単語をすべてバリアントに集めて、必要に応じて終わるまで、配列を単純に下っていきます。
検索は最初の位置がバイナリ検索によって決定される辞書の限られた部分を通過するため、3つのサブ辞書でも、4文字目以降をノックアウトする場合の検索は致命的なボトルネックではなくなりました。
メモリ/速度の許容可能な妥協点は、3〜4個のサブ辞書を使用することです。
「ハエ」-「ゾウ」の変換の図 ：
| 構成 | Tロード辞書 | T検索 | T合計 | RAMの消費 |
|---|---|---|---|---|
| 基本辞書のみ | 0.02秒 | 137秒 | 137秒 | 6 Mb |
| 1つの辞書 | 0.61秒 | 16.40秒 | 17.01秒 | 25 Mb |
| 2つの辞書 | 1.20秒 | 4.73秒 | 5.93秒 | 44 Mb |
| 3つの辞書 | 1.85秒 | 2.72秒 | 4.57秒 | 62 Mb |
| 4辞書 | 2.42秒 | 0.82秒 | 3.24秒 | 79 Mb |
| 5サブワード | 2.98秒 | 0.77秒 | 3.75秒 | 97 Mb |
チェーン：「ハエ」-「ムラ」-「トラック」-「ハンディキャップ」-「樹皮」-「トウモロコシ」-「コアーン」-「クラン」-「クローン」-「象」（9トランジション）
もちろん、4文字のハエとゾウを回すのに5番目の辞書（単語から5番目の文字が削除され、結果の辞書が再ソートされる）は必要ないことは絶対に理にかなっています。 しかし、別の例を見てみましょう。
比較のために、「松」から「タンパク質」への変換：
-4つのサブ辞書の場合：ダウンロード2.41秒、検索1.07秒、合計3.48秒
-5つのサブ辞書の場合：ダウンロード3.01秒、検索0.36秒、合計3.37秒
つまり 5番目の辞書は、辞書、キャッシュ、およびアルゴリズムのストレージを最適化した後にのみ追加できます。 そして今、彼はRAMの過剰消費に過ぎません。
しかし...しかし、「それはどういうわけか私の膝の上で何とか耐えられる程度に機能するバージョンです」それは私に合わなかった。 そして、私はハエのゾウへの変換を完璧にし続けました。
最初のバージョン （PHP 5.4）
*
*リラックスした目、一杯のコーヒー、そしてその精神で一時停止するのは良いことです
*
象の耳を描いた口紅
第二に、トランク、テール、そして今
ピンクのハエが寝室を飛ぶ
それはドアにぶつかって頭を叩きます。
kekc @ hohmodrom.ru
第二版
私はたくさんとかしました。
チェックを追加しました。
静かに理解できない死の代わりに、例外を投げることを追加しました。
構成を強調表示しました。
データベースに切り替える準備-データロジックを別のマッパーに組み込みました。
等 アーキテクチャ上。
しかし、これは面白くありません。 ここで最も興味深い変更は、パーサー、ランダムネスファクター、および文字の周波数特性に基づく推定関数です。
1）パーサー
ソース辞書は十分に大きいですが、何らかの理由で一般的な単語すら存在しないことに気付きました。 そして注意））） 象はいませんでした ！ 象が、 象が、象がおっと。 差別
はい、設定された目標を達成するために（フライを使って象を作るため）、最初のバージョンでは、特徴的なチェーンの回答をグーグルで検索しなければなりませんでした。
[そして、はい、この辞書で初めて（setlocaleとmb_stringの正しいロケールにもかかわらず、後続のphpソートコーンから）の単語が突然辞書の最後にあることにつまずきました。]
技術的な使用に適した辞書からではなく、少なくともどこからでも、追加の単語を使用してこの点を修正することにしました。
多くのリンクがchyjik.narod.ru/index.htmにつながりましたが、彼はその年にNarod.ruを購入し、それを発酵の目的で破壊した邪悪なYandexによって長年突然忘れられていました。
しかし、ここでは素晴らしいWebアーカイブが役に立ちました。彼に感謝します。
保存された「クロスワード辞書」全体を保存し、data / psrc /に保存し、通常のスケジュールでparse.phpを作成しました（これは何度も修正しました。なぜなら、そのサイトはMS Wordで、レイアウトがまったく同じではありませんでした）、-パーセントの辞書を50％拡大しました。
2）ランダムネス係数
チェーンは常に同じであることが判明しました。これは一般に明らかです。 「プレイ」し、「突然良くなる」ことを可能にするために、彼は評価関数にmt_randのランダム係数を導入しました。 もっと面白くなった。 時々、私がこれまで知らなかった新しい、より短い鎖が本当に見えました。
もちろん、マイナス面があります-不快なカップルには検索があり、チェーンが見つかりません。 または、通常よりも少し長くなります。 しかし、それでもメインケースは非常に安定しています。
より具体的には、ランダム性が「非常に軽く」導入されました-新しい世代のフィットネスを注文するときの比較関数で-同じフィットネススコアを持つ単語がランダムな順序で配列され始めました。
ランダム要素
// " " ( ) usort($mutationChains, function($a, $b) { $diff = $b['score'] - $a['score']; return $diff ? $diff : mt_rand(-1, 1); });
3）評価関数
FLYから、エレファントは10のトランジション内でかなり鮮明にうまくいきました。
しかし（！）
FLYから音節という単語が得られました...頑固に60-70（！）に移行します。
しかし、エレファントよりも1だけ長くする必要があることは明らかです。 男は明らかです。 車はありません、それはアルゴリズムによるものです。 アルゴリズムエラー。 評価関数エラー。
彼は多くの実験をしました、私は隠しません。
スコアが5桁短くなり、得点に疑わしい変更が加えられました。 しかし、これは必要な結果ではありません。
明らかに、調整の問題は夏以降解決されていない、と私は考えた。 問題は何ですか。 違いは何ですか。 最後の手紙の違い、はい、事実。 言葉があり、ここに言葉があります。 これらの文字はどのように異なっているので、すべてがとても悪いのですか...
そうだね。 使用頻度！ そして、それに応じて、関連する変異バリアントの数。 つまり、「G = Gの点で完全なヒット」は、「H、M、K、...！= Gのヒットではない」よりも悪いか、少なくとも「適合性」を評価するのにあまり良くない場合があります。 しかし、もちろん、「ヒットしないY、b、u、...！= G」よりもはるかに優れています。
wikiからの文字を使用する頻度の表を取りました。 （実際には、これは完全に正しいわけではありません。名詞の既存の辞書に従って頻度を考慮する必要がありますが、基本的な違いはほとんどありません）。 コードにあるとおりにed打。 あまり美しくありません、はい。しかし、ここまでにしてください。 母音と子音に従って、文字の頻度を正規化された配列にカットし、最も一般的な母音/子音に正規化します。 評価機能を書き直しました。 IS！ 象+ 1！
はい、そして象自体がさらに1つまたは2つのステップを早く始めました。
文字の頻度を使用する
初期化時：
評価関数：
public function __construct() { //$this->_mprDictionary = null; $this->_mprDictionary = new DictionaryFileMapper(); $this->_vovels = ""; $this->LoadLetterFrequencies(); } private function LoadLetterFrequencies() { $this->_lettersFrequences = [ '' => 0.10983, '' => 0.08483, '' => 0.07998, '' => 0.07367, '' => 0.06700, '' => 0.06318, '' => 0.05473, '' => 0.04746, '' => 0.04533, '' => 0.04343, '' => 0.03486, '' => 0.03203, '' => 0.02977, '' => 0.02804, '' => 0.02615, '' => 0.02001, '' => 0.01898, '' => 0.01735, '' => 0.01687, '' => 0.01641, '' => 0.01592, '' => 0.01450, '' => 0.01208, '' => 0.00966, '' => 0.00940, '' => 0.00718, '' => 0.00639, '' => 0.00486, '' => 0.00361, '' => 0.00331, '' => 0.00267, '' => 0.00037, '' => 0.00013, ]; // $this->_lettersFrequencesVovel = []; $this->_lettersFrequencesConsonant = []; foreach ($this->_lettersFrequences as $letter => $frequency) { if ($this->IsVovel($letter)) { $this->_lettersFrequencesVovel[$letter] = $frequency; } else { $this->_lettersFrequencesConsonant[$letter] = $frequency; } } // . // , $maxFrequency = reset($this->_lettersFrequencesVovel); foreach ($this->_lettersFrequencesVovel as $letter => &$frequency) { $frequency /= $maxFrequency; } $maxFrequency = reset($this->_lettersFrequencesConsonant); foreach ($this->_lettersFrequencesConsonant as $letter => &$frequency) { $frequency /= $maxFrequency; } } /** * * * @param string $letter - * @return bool */ public function IsVovel($letter) { return false === mb_strpos($this->_vovels, $letter) ? false : true; }
評価関数：
/** * * * @param string $word - * @param string $comparationWord - * @return int */ public function GetWordScore($word, $comparationWord) { // - , - static $cachedComparationWord = ''; static $wordLen = 0; static $cwLetters = []; if ($cachedComparationWord != $comparationWord) { $cachedComparationWord = $comparationWord; $wordLen = mb_strlen($comparationWord); $cwLetters = []; for ($i = 0; $i < $wordLen; $i++) { $letter = mb_substr($comparationWord, $i, 1); $cwLetters[$i] = [ 'letter' => $letter, 'isVovel' => false === mb_strpos($this->_vovels, $letter) ? false : true, ]; } } $score = 0; for ($i = 0; $i < $wordLen; $i++) { $letter = mb_substr($word, $i, 1); $isVovel = $this->IsVovel($letter); // = 3 if ($letter == $cwLetters[$i]['letter']) { $score += 1; if ($isVovel) { $score += 2 + 1 * $this->_lettersFrequencesVovel[$letter]; } else { $score += 0 + 3 * $this->_lettersFrequencesConsonant[$letter]; } continue; } if ($isVovel) { if ($cwLetters[$i]['isVovel']) { // = 2 $score += 2 + 2 * $this->_lettersFrequencesVovel[$letter]; } else { // = 1 $score += 2 * $this->_lettersFrequencesVovel[$letter]; } } else { if (isset($this->_lettersFrequencesConsonant[$letter])) { $score += 3 * $this->_lettersFrequencesConsonant[$letter]; } } } return round($score); }
«»-«»:
| 構成 | T | T | T | |
|---|---|---|---|---|
| 0,04 | 210 | 210 | 9 | |
| 1 | 0,98 | 26,16 | 27,14 | 42 |
| 2 | 1,97 | 9,97 | 11,94 | 72 |
| 3 | 2,98 | 4,72 | 7,70 | 102 |
| 4 | 3,97 | 1,37 | 5,34 | 130 |
| 5 | 4,96 | 1,30 | 6,26 | 158 |
: «» — «» — «» — «» — «» — «» — «» — «» (7 ).
, ( 0,68 1,03 , +51%), . , , , — , , , .
, , 4 . . , . , , .
2- ( PHP 5.4).
*
* , .
* ,
* , .
*
:
, ,
.
…
- !
, . - ( MySQL 5.5) , , .
1) ?
, memcache — , , , - mysql-. , .
— 4 . 0,8 . MySQL, «» 0,002 0.95 . , , - , .
-- -- : `metagram` -- -- -------------------------------------------------------- -- -- `dictionary` -- CREATE TABLE IF NOT EXISTS `dictionary` ( `id` int(11) NOT NULL AUTO_INCREMENT, `name` varchar(255) NOT NULL, `lang` varchar(30) NOT NULL, PRIMARY KEY (`id`), UNIQUE KEY `name` (`name`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8 AUTO_INCREMENT=1 ; -- -------------------------------------------------------- -- -- `word` -- CREATE TABLE IF NOT EXISTS `word` ( `id` int(11) NOT NULL AUTO_INCREMENT, `value` varchar(50) NOT NULL, `description` varchar(255) DEFAULT NULL, `dictionary_id` int(11) NOT NULL, `length` smallint(6) NOT NULL, PRIMARY KEY (`id`), UNIQUE KEY `value` (`value`), KEY `dictionary_id` (`dictionary_id`), KEY `lenght` (`length`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8 AUTO_INCREMENT=1 ; -- -------------------------------------------------------- -- -- `word_pseudo` -- CREATE TABLE IF NOT EXISTS `word_pseudo` ( `id` int(11) NOT NULL AUTO_INCREMENT, `value` varchar(50) NOT NULL, `word_id` int(11) NOT NULL, `deleted_symbol_pos` smallint(6) NOT NULL, PRIMARY KEY (`id`), UNIQUE KEY `value_word_id` (`deleted_symbol_pos`,`value`,`word_id`), KEY `word_id` (`word_id`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8 AUTO_INCREMENT= 1 ;
, 1 5 .
2)
, , 2 , - SELECT . MySQL- . , , . .
DictionaryMysqlMapper
... private $_cachedWords; private $_cachedWordKeys; ... /** * * * @param string $key () * @return string|false|null */ public function GetWord($key) { if (isset($this->_cachedWords[$key])) { return $this->_cachedWords[$key]; } $wordRow = $this->_db->FetchOne("SELECT * FROM `word` WHERE `id` = " . $this->_db->QuoteValue($key)); $this->_cachedWords[$key] = $wordRow['value']; return $wordRow['value']; }
3)
, , 100 50 . , 20 , 50.
. 1 0,5-0,6 .
だから
3- ( PHP 5.4, MySQL 5.5)
*
* , , « » )
* .
*
,
とても
:
—
!
() , « »
まとめ
PHP 5.4 + MySQL 5.5, 0,5 . 9 :
'from' => "" 'to' => "" 'runMode' => "MySQL" 'list' ... '0' => "" '1' => "" '2' => "" '3' => "" '4' => "" '5' => "" '6' => "" '7' => "" '8' => "" 'timeLoad' => ", : 0,008000 ." 'time' => " : 0,551032 ." 'status' => "."
, PHP ( 100 ), . , , .
次は？
, , . :
- , : , . , 2-4 . , , .
- ? . . , — . . , , .
- Redis? Memcached?
- N ,
- ? , . .
- CP1251? Utf-8 . , , , . 1 , 2 . .
- JavaScript ? , , — , , .
- C++?
- , .
… , . , , Diamond-Square .
PS：
, , .
! - . ご清聴ありがとうございました。