私はユーザーが入力する単語が有効な英語の単語であることを検証する必要があるHTML5ゲームを設計しています。私は、私はユーザーの種類として検証を行いたいので、私はサーバーに単語を送信することによって検証を行うことができます知っている、サーバー側の検証は最適なソリューションではありません。したがって、ユーザーのブラウザで実行されているゲームで検証を実行する必要があります。単語が有効な英語の単語であるかどうかを判断するためのアルゴリズム/データ構造
ユーザが入力した単語を英語のすべての単語に対して検証する最も効率的な方法は何ですか？
はい、検索可能な単語のツリーを作成し、O(|P|)時間の要素を検索する場合など、trieなどのデータ構造を使用できます。なぜあなたがあなた自身に尋ねるなら、トライはより良い選択です。あなたは一度に1人のキャラクターを入力するたびに手紙を手紙でたどり、あなたのゲームルールに従って速いフィードバックを与えることができます。
P: pattern you are searching for.
また、あなたは、サーバー側の検証ができないと述べたが、私は、彼らはAjaxが言葉を検証し、その時点で彼らは画面上にポップアップ表示いくつかのことや、いくつかのゲームのストーリーを作成したりするために呼び出しを作るゲームを見てきましたコンポーネントを使用すると、即座に、または面白い方法で即座に起こっていると感じるようになります。
trieは使用する理論的に正しいデータ構造ですが、コンピュータの/ usr/share/dict/wordsは1 MB未満。それを解凍するために使用できるzlibの純粋なJS実装があります。バイナリ検索アルゴリズムは、辞書内の特定の単語を見つけるために20回以下の呼び出しを行います。これは、ブラウザでインタラクティブに使用するのに十分速いものです。
ブラウザでこれを実装するには十分です。
このようなタスクのアルゴリズムは、Bloom filterです。難しい部分は適切な辞書を組み立てることになることに注意してください。
このためにBloomフィルタを使用する方法を記述する必要があります。また、誤検出の問題も解決する必要があります。 –
トライですか？ユーザーが入力する手紙で手紙を行うことができます。 – jwimberley
「ユーザーの種類として検証する」とはどういう意味ですか？ユーザーが「th」と入力すると、「th」で始まる単語があるため何もしませんが、ユーザーが「f」と入力すると、入力が無効であることがわかる"thf"で始まる英語の単語はありませんか？ –
いいえ。妥当性検査とは、ユーザーが入力したときに現在表示されているものが有効であるかどうかを検証することを意味します。ユーザーが入力すると、オンスクリーンのインジケータが常に更新されます。単語が無効であれば赤、単語が有効であれば緑で表示されます。したがって、ユーザーが入力すると、タイプされている単語に応じて、インジケータが赤と緑の間で複数回切り替わる場合があります。 –