ほとんどのコード エディターは、Boyer-Moore アルゴリズムを使用して文字列検索を実装していることを知っています。文字列置換アルゴリズムをどのように実装していますか?
1 に答える
1
最近のほとんどのテキスト エディタは、単一のメモリ ブロックを使用してファイル全体を保持するか、行の配列またはより大きなサイズのブロックを使用して、それぞれが独自のメモリ ブロックを指していると思います。(過去には、もっと興味深いテクニックが採用されていました。1 つの方法は、カーソル位置の左または上にあるすべてのテキストを固定サイズのバッファーの左端に「押し付けて」、すべてのテキストを右または下に配置することです。"次に、文字を挿入または削除する一般的な操作を一定時間で行うことができます! カーソル k 位置を右に移動すると、カーソルの左端から k バイトがスライドします。右セグメントを左セグメントの右端に移動します。つまり、カーソルの移動は線形時間操作になりました!)
テキストが「通常の」方法で格納されていると仮定すると (つまり、上記の左右のカーソル依存バッファーのペアではない)、特に置換テキストが検索より長い場合、置換操作を最適化する方法はあまりありません。テキスト -- この場合、行/ブロック/ファイルの残りの部分は、置換ごとにメモリ内で先送りしなければならないという事実から逃れることはできません。そこでできる最善のことは、複数の O(n) コピー操作を避けることです。検索文字列を削除してから、置換文字列を一度に 1 文字ずつ挿入し、残りの行/ブロック/ドキュメントを一度に 1 文字ずつ先に進めます。後者のステップには O(n^2) 時間がかかるためです。代わりに、1 つの O(n) ステップで置換文字列のためのスペースを確保するために、ドキュメント テキストの残りの部分を十分前方にシャントします。
置換文字列が検索テキストよりも短い場合は、2 つのポインターfromとを使用して順方向にスキャンしto、常に一方から他方にコピーできます。交換が行わtoれると、遅れが出始めfromます。これはto <= from常に保持されるため安全であり、後で読まなければならないものを上書きすることはありません。
実際には、置換文字列が検索文字列よりも長く、検索文字列のサフィックスが検索文字列のプレフィックスでもない場合、1 回の O(n) パスで安全に末尾から逆方向にスキャンできます。接尾辞/接頭辞の要件は、次のような状況を回避するために必要であり、スキャン方向に応じて異なる動作が発生します。
Search and replace "abcabc" with "xyz" in document text "abcabcabc":
S&R using forward algo gives: xyzabc
S&R using backward algo gives: abcxyz
于 2013-09-05T12:26:07.710 に答える