75352


お世話になっております。  
実質的に置換と同じことで遙かに処理の速い方法はありますでしょうか？

事例 たとえば以下のようにテキストの置換パターンが複数あったとします。

[code]

    08A54G→タナ
    08A→タ
    54G→ナ
    
[/code]

テキストエディタの置換のマクロでも変換していけますが、数百万字だとけっこう時間がかかります。  
かかる時間とは、テキストエディタや連続置換であるかにもよりますが、速くて5分以上です。

しかし、C++などで作ったアプリなら、これと同じ表示を1秒もかからず変換できたりします。  
おそらくこの仕組みは置換とは別の方法だと思いますので、その処理方法の名前を知りたいのです。

上記のようなルールのこれらのパターンを一瞬で置き換えて表示する方法はPythonなどのインタプリタでありますでしょうか？  
よろしくお願いいたします。


CC BY-SA 4.0
2021-04-17T11:44:06.353
75344
2021-04-18T04:53:09.283
2021-04-18T00:31:17.483
19110
43999
question
アルゴリズム
エディタの「置換」機能と実質的に同じことをより速く処理する方法はありますでしょうか？


> しかし、C++などで作ったアプリなら、これと同じ表示を1秒もかからず変換できたりします。

テキストエディタはあくまでテキストを編集するためのものです。置換マクロの実装にも依りますが、１つ１つの置換の結果を画面表示に反映している場合、画面表示自体に時間がかかります。  
逆にC++などが高速なのは、表示機能を持たせていない、もしくは最終結果のみの表示でテキストの編集機能を持たないからではないでしょうか？

結局、質問者さんが何をやりたいか、やりたいことに対してテキストエディタを選択するのが適切かどうか、そこに依存します。

* * *

質問文が編集されいつのまにかアルゴリズムタグが付けられてしまっていますが、テキストエディタの置換マクロとC++などとにアルゴリズム的な差異はないと思われます。C++で実現しようとしたアルゴリズムと同様のものを置換マクロで実装すればいい話です。  
もし質問文では言及されていない、特定のテキストエディタの置換マクロに機能的制約があり、C++と同等の実装ができないとしたら、それは単にそのテキストエディタ固有の制限というだけの話であり、テキストエディタ全般に適用される話ではありません。

逆に当初、自然言語処理タグが付けられていましたが、[Wikipediaの自然言語処理](https://ja.wikipedia.org/wiki/%E8%87%AA%E7%84%B6%E8%A8%80%E8%AA%9E%E5%87%A6%E7%90%86)から引用しますと

> 自然言語処理（natural language
> processing）は、人間が日常的に使っている自然言語をコンピュータに処理させる一連の技術であり、人工知能と言語学の一分野である。 ...
> データベース内の情報を自然言語に変換したり、自然言語の文章をより形式的な（コンピュータが理解しやすい）表現に変換するといった処理が含まれる。応用例としては予測変換、IMEなどの文字変換が挙げられる。

となっていて、質問の文字列置換とは全く別分野であることを理解すべきです。


CC BY-SA 4.0
2021-04-17T23:52:58.270
75351
2021-04-18T04:53:09.283
2021-04-18T04:53:09.283
4236
4236
75344
answer


処理方法の名前は[ボイヤー-
ムーア法](https://ja.wikipedia.org/wiki/%E3%83%9C%E3%82%A4%E3%83%A4%E3%83%BC-%E3%83%A0%E3%83%BC%E3%82%A2%E6%96%87%E5%AD%97%E5%88%97%E6%A4%9C%E7%B4%A2%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)、[Bitapアルゴリズム](https://ja.wikipedia.org/wiki/Bitap%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)など、文字列検索アルゴリズムがあります。

しかし高々数百万字に対して5分以上は時間がかかりすぎです。  
パソコンのスペックや置換パターンの数によりますが、一番原始的な[ブルートフォース検索](https://ja.wikipedia.org/wiki/%E5%8A%9B%E3%81%BE%E3%81%8B%E3%81%9B%E6%8E%A2%E7%B4%A2)アルゴリズムを用いても置換処理自体は数秒以内に完了するでしょう。

どちらかというと下記の情報処理技術者向け用語の方がお求めの回答かもしれません。

  * アクセス速度  
「1文字置換するたびにファイル書き出しとファイル読み込みを行い、それを数百万回繰り返す」処理と  
「数百万文字をメモリ上に配置してから置換する」処理では、文字通り桁違いに処理時間が変わります。  
参考: [各種メモリ／ストレージのアクセス時間，所要クロックサイクル，転送速度，容量の目安 -
まとめ](https://qiita.com/zacky1972/items/e0faf71aa0469141dede#%E3%81%BE%E3%81%A8%E3%82%81)

  * 描画コスト  
他の回答にあるように、もしもテキストエディタで「1文字置換する」→「数百万文字をエディタ上に再描画する」→「1文字置換する」→「数百万文字をエディタ上に再描画する」→...を数百万回繰り返していると非常に処理速度が遅くなります。  
5分以上かかる原因もおそらくそれです。  
「一瞬で」処理が完了する処理は置換中に描画を行わず、置換後に描画する(あるいは描画自体を行わない)仕組みです。コメントにある`pipe`による高速化はその意味でも有効です。

  * マルチスレッド  
上記のように置換と再描画を連続して行うと時間がかかりますが、置換処理するプロセスと並行して別のプロセスで再描画を行う処理にすることで速度の改善が見込めます。  
他にも数百万文字を例えば1万文字ごとに分割して複数のプロセスで置換してから最後に結合するなど、マルチスレッド処理を適切に用いることで高速化することができます。ただしこちらは1万文字ごとの切れ目を適切に処理するよう注意が必要です。


CC BY-SA 4.0
2021-04-18T01:30:12.230
75352
2021-04-18T01:30:12.230
9820
75344
answer