辞書の単語の一般的なトライが構築されていると仮定すると、スペルミスの4つのケース（トラバーサル中の置換、削除、転置、挿入）をチェックするための最良の方法は何でしょうか？
1つの方法は、特定の単語のn個の編集距離内にあるすべての単語を把握し、Trieでそれらをチェックすることです。これは悪いオプションではありませんが、ここでのより良い直感は、トラバーサル中に単語を変更した後、動的計画法（または再帰的な同等の方法）を使用して最適なサブトライを決定することです。
どんなアイデアでも大歓迎です！
PS、回答のリンクだけでなく、実際の入力をいただければ幸いです。
先日、これを行うためのコードを実際に作成しました。
https://bitbucket.org/teoryn/spell-checker/src/tip/spell_checker.py
Peter Norvig（ http://norvig.com/spell-correct.html ）のコードに基づいていますが、指定された編集距離内の単語をより速く見つけるために、辞書をトライに格納します。
アルゴリズムは、入力された単語から文字を消費することにより、途中の各ステップで可能な編集を再帰的に適用する（またはしない）トライをウォークします。再帰呼び出しのパラメーターは、さらに何回編集できるかを示します。トライは、指定されたプレフィックスから実際に到達できる文字をチェックすることにより、検索スペースを狭めるのに役立ちます。たとえば、文字を挿入する場合、アルファベットの各文字を追加する代わりに、現在のノードから到達可能な文字のみを追加します。編集を行わないことは、入力単語からの現在の文字に沿って、トライ内の現在のノードから分岐を取得することと同じです。そのブランチがない場合は、バックトラックして、実際の単語が見つからない可能性のある大きなスペースの検索を回避できます。
これは、ツリーでの単純な幅優先探索で実行できると思います。探しているエラーの数のしきい値を選択し、一度に1つずつ一致する単語の文字を調べて、次のセットを生成します。 （プレフィックス、サブトライ）ペアはこれまでにプレフィックスと一致し、エラーしきい値を下回っている間に、次のサブゴールのセットに追加します。
これはかなりナイーブなようです。動的計画法を考えるようになった問題はありますか？
単語内の連続する各文字がツリー内の1つのレベルを表すと仮定すると、各文字でチェックする5つのケース（一致、削除、挿入、置換、転置）があります。転置は2つの隣接する文字であると想定しています。
チェックするツリーノードと文字を受け入れる関数（CheckNode）が必要になります。一致を表す（子/孫）ノードのセットを返す必要があります。
単語を受け入れる関数（CheckWord）が必要になります。各文字をノードのセットに対して順番にチェックします。一致した単語を表す（リーフ）ノードのセットを返します。
ツリーの各レベル（子、孫など）は、単語内の文字の位置と一致するという考え方です。トップレベルのツリーノードをレベル0と呼ぶと、レベル1、レベル2などになります。
明らかにエラーのない単語の場合、ツリー内の文字の位置とレベルの間に1対1の一致があります。
削除する場合は、ツリーのレベルをスキップする必要があります。
挿入の場合、単語内の文字をスキップする必要があります。
置換の場合、レベルと文字の両方をスキップする必要があります。
転置の場合、単語内の文字を（一時的に）入れ替える必要があります。
2つのシーケンス間の距離を見つけるための動的計画法ソリューションを提供するレーベンシュタイン距離の計算を見てください。