一般的な部分式の削除の実装

Question

大きな数式（数百万のノード）に対応する式グラフの共通部分式消去（CSE）の実装を検討しています。

これを実行するにはどのようなアルゴリズムが適していますか？インターネットを検索して簡単にアルゴリズムを実装していましたが、何も見つかりませんでした。可能であれば、アルゴリズムは完全な式グラフのノード数に線形の複雑さを持たなければならない。

Answer 1

これは副作用のない表現ですか？そして、最も簡単なことは、各部分式の木をバケットにハッシュして、部分式除去の候補を決定することです。 これはCSEの特別なケースです。すべての式が単一の（巨大な）「基本ブロック」に含まれています。 （私はduplicate codeを検出するための基礎としてこの考え方を使用しています）

式に順序と副作用がある場合は、Value Numberingと考えるとよいでしょう。