algorithm - 数式を単純化するための戦略

Question

数式を表す整形式のツリーがあります。たとえば、文字列：を指定する"1+2-3*4/5"と、これは次のように解析されます。

subtract(add(1,2),divide(multiply(3,4),5))

これはこのツリーとして表されます：

私がやりたいのは、この木を取り、可能な限り減らすことです。上記の場合、すべての数値が定数であるため、これは非常に簡単です。$ただし、不明なもの（後に識別子が続くことで示される）を許可すると、状況はさらに複雑になり始めます。

"3*$a/$a"になりますdivide(multiply(3,$a), $a)

用語は互いに打ち消し合う必要があるため3、これは単純化してになります。$a問題は、「これを一般的な方法で認識するにはどうすればよいですか？」です。min(3, sin($x))それが常に起こることをどのように認識しますsin($x)か？それをどのように認識しsqrt(pow($a, 2))ますabs($a)か？nthroot(pow(42, $a), $a)（42の3^乗の3乗）がであるとどのように認識し42ますか？

この質問はかなり広いと思いますが、私はしばらくの間これに頭を悩ませていて、十分に満足のいくものを思い付いていません。

Answer 1

おそらく、用語書き換えシステムを実装したいと思うでしょう。基礎となる数学については、WikiPediaをご覧ください。

用語書き換えモジュールの構造

最近ソリューションを実装したので...

• まず、式の構造をモデル化するクラスCExpressionを準備します。

• CRuleパターンと置換を含むを実装します。パターン変数として特別なシンボルを使用します。これは、パターンマッチング中にバインドされ、置換式で置換される必要があります。

• 次に、クラスを実装しCRuleます。これは主なメソッドapplyRule(CExpression, CRule)であり、ルールを適用可能な式の部分式と照合しようとします。一致する場合は、結果を返します。

• 最後に、クラスを実装しCRuleSetます。これは、単にCRuleオブジェクトのセットです。mainメソッドreduce(CExpression)は、これ以上ルールを適用できない限り、ルールのセットを適用してから、縮小された式を返します。

• CBindingEnvironmentさらに、すでに一致したシンボルを一致した値にマップするクラスが必要です。

式を通常の形式に書き直してみてください

このアプローチはある程度は機能しますが、完全ではない可能性が高いことを忘れないでください。これは、以下のすべてのルールがローカル用語の書き換えを実行するという事実によるものです。

このローカル書き換えロジックを強化するには、式を通常の形式と呼ぶものに変換する必要があります。これが私のアプローチです：

• 用語にリテラル値が含まれている場合は、用語をできるだけ右に移動してみてください。

• 最終的に、このリテラル値は右端に表示される可能性があり、完全なリテラル式の一部として評価できます。

完全リテラル式を評価する場合

興味深い質問は、完全にリテラルの式をいつ評価するかです。あなたが式を持っているとしましょう

   x * ( 1 / 3 )

これはに減少します

   x * 0.333333333333333333

ここで、xが3に置き換えられたとします。これにより、次のような結果が得られます。

   0.999999999999999999999999

したがって、熱心な評価はわずかに不正確な値を返します。

反対側で、（1/3）を保持し、最初にxを3に置き換える場合

   3 * ( 1 / 3 )

書き換えルールは

   1

したがって、完全にリテラルの式を遅く評価することが役立つ場合があります。

書き換えルールの例

アプリケーション内でのルールの表示方法は次のとおりです。_1、_2、...記号は任意の部分式と一致します。

addRule( new TARuleFromString( '0+_1',   // left hand side  :: pattern
                               '_1'      // right hand side :: replacement
                             ) 
       );

またはもう少し複雑

addRule( new TARuleFromString( '_1+_2*_1', 
                               '(1+_2)*_1' 
                             ) 
       );

特定の特殊記号は、特殊な部分式にのみ一致します。例：_Literal1、_Literal2、...はリテラル値のみに一致します：

addRule( new TARuleFromString( 'exp(_Literal1) * exp(_Literal2 )', 
                               'exp( _Literal1 + _Literal2 )' 
                             ) 
       );

このルールは、非文字表現を左に移動します。

addRule( new TARuleFromString( '_Literal*_NonLiteral', 
                               '_NonLiteral*_Literal' 
                             ) 
       );

'_'で始まる名前は、パターン変数です。システムはルールに一致しますが、すでに一致したシンボルの割り当てのスタックを保持します。

最後に、ルールによって終了しない置換シーケンスが生成される可能性があることを忘れないでください。したがって、式を減らしながら、プロセスに、以前にすでに到達した中間式を記憶させます。

私の実装では、中間式を直接保存しません。中間式のMD5（）ハッシュの配列を保持します。

出発点としての一連のルール

開始するための一連のルールは次のとおりです。

            addRule( new TARuleFromString( '0+_1', '_1' ) );
            addRule( new TARuleFromString( '_Literal2=0-_1', '_1=0-_Literal2' ) );
            addRule( new TARuleFromString( '_1+0', '_1' ) );
            
            addRule( new TARuleFromString( '1*_1', '_1' ) );
            addRule( new TARuleFromString( '_1*1', '_1' ) );
            
            addRule( new TARuleFromString( '_1+_1', '2*_1' ) );
            
            addRule( new TARuleFromString( '_1-_1', '0' ) );
            addRule( new TARuleFromString( '_1/_1', '1' ) );
            
            // Rate = (pow((EndValue / BeginValue), (1 / (EndYear - BeginYear)))-1) * 100 

            addRule( new TARuleFromString( 'exp(_Literal1) * exp(_Literal2 )', 'exp( _Literal1 + _Literal2 )' ) );
            addRule( new TARuleFromString( 'exp( 0 )', '1' ) );
            
            addRule( new TARuleFromString( 'pow(_Literal1,_1) * pow(_Literal2,_1)', 'pow(_Literal1 * _Literal2,_1)' ) );
            addRule( new TARuleFromString( 'pow( _1, 0 )', '1' ) );
            addRule( new TARuleFromString( 'pow( _1, 1 )', '_1' ) );
            addRule( new TARuleFromString( 'pow( _1, -1 )', '1/_1' ) );
            addRule( new TARuleFromString( 'pow( pow( _1, _Literal1 ), _Literal2 )', 'pow( _1, _Literal1 * _Literal2 )' ) );

//          addRule( new TARuleFromString( 'pow( _Literal1, _1 )', 'ln(_1) / ln(_Literal1)' ) );
            addRule( new TARuleFromString( '_literal1 = pow( _Literal2, _1 )', '_1 = ln(_literal1) / ln(_Literal2)' ) );
            addRule( new TARuleFromString( 'pow( _Literal2, _1 ) = _literal1 ', '_1 = ln(_literal1) / ln(_Literal2)' ) );

            addRule( new TARuleFromString( 'pow( _1, _Literal2 ) = _literal1 ', 'pow( _literal1, 1 / _Literal2 ) = _1' ) );
            
            addRule( new TARuleFromString( 'pow( 1, _1 )', '1' ) );

            addRule( new TARuleFromString( '_1 * _1 = _literal', '_1 = sqrt( _literal )' ) );
            
            addRule( new TARuleFromString( 'sqrt( _literal * _1 )', 'sqrt( _literal ) * sqrt( _1 )' ) );
            
            addRule( new TARuleFromString( 'ln( _Literal1 * _2 )', 'ln( _Literal1 ) + ln( _2 )' ) );
            addRule( new TARuleFromString( 'ln( _1 * _Literal2 )', 'ln( _Literal2 ) + ln( _1 )' ) );
            addRule( new TARuleFromString( 'log2( _Literal1 * _2 )', 'log2( _Literal1 ) + log2( _2 )' ) );
            addRule( new TARuleFromString( 'log2( _1 * _Literal2 )', 'log2( _Literal2 ) + log2( _1 )' ) );
            addRule( new TARuleFromString( 'log10( _Literal1 * _2 )', 'log10( _Literal1 ) + log10( _2 )' ) );
            addRule( new TARuleFromString( 'log10( _1 * _Literal2 )', 'log10( _Literal2 ) + log10( _1 )' ) );

            addRule( new TARuleFromString( 'ln( _Literal1 / _2 )', 'ln( _Literal1 ) - ln( _2 )' ) );
            addRule( new TARuleFromString( 'ln( _1 / _Literal2 )', 'ln( _Literal2 ) - ln( _1 )' ) );
            addRule( new TARuleFromString( 'log2( _Literal1 / _2 )', 'log2( _Literal1 ) - log2( _2 )' ) );
            addRule( new TARuleFromString( 'log2( _1 / _Literal2 )', 'log2( _Literal2 ) - log2( _1 )' ) );
            addRule( new TARuleFromString( 'log10( _Literal1 / _2 )', 'log10( _Literal1 ) - log10( _2 )' ) );
            addRule( new TARuleFromString( 'log10( _1 / _Literal2 )', 'log10( _Literal2 ) - log10( _1 )' ) );
            
        
            addRule( new TARuleFromString( '_Literal1 = _NonLiteral + _Literal2', '_Literal1 - _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_Literal1 = _NonLiteral * _Literal2', '_Literal1 / _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_Literal1 = _NonLiteral / _Literal2', '_Literal1 * _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_Literal1 =_NonLiteral - _Literal2',  '_Literal1 + _Literal2 = _NonLiteral' ) );

            addRule( new TARuleFromString( '_NonLiteral + _Literal2 = _Literal1 ', '_Literal1 - _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_NonLiteral * _Literal2 = _Literal1 ', '_Literal1 / _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_NonLiteral / _Literal2 = _Literal1 ', '_Literal1 * _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_NonLiteral - _Literal2 = _Literal1',  '_Literal1 + _Literal2 = _NonLiteral' ) );
            
            addRule( new TARuleFromString( '_NonLiteral - _Literal2 = _Literal1 ', '_Literal1 + _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_Literal2 - _NonLiteral = _Literal1 ', '_Literal2 - _Literal1 = _NonLiteral' ) );
            
            addRule( new TARuleFromString( '_Literal1 = sin( _NonLiteral )', 'asin( _Literal1 ) = _NonLiteral' ) );
            addRule( new TARuleFromString( '_Literal1 = cos( _NonLiteral )', 'acos( _Literal1 ) = _NonLiteral' ) );
            addRule( new TARuleFromString( '_Literal1 = tan( _NonLiteral )', 'atan( _Literal1 ) = _NonLiteral' ) );

            addRule( new TARuleFromString( '_Literal1 = ln( _1 )', 'exp( _Literal1 ) = _1' ) );
            addRule( new TARuleFromString( 'ln( _1 ) = _Literal1', 'exp( _Literal1 ) = _1' ) );
            
            addRule( new TARuleFromString( '_Literal1 = _NonLiteral', '_NonLiteral = _Literal1' ) );

            addRule( new TARuleFromString( '( _Literal1 / _2 ) = _Literal2', '_Literal1 / _Literal2 = _2 ' ) );
            
            addRule( new TARuleFromString( '_Literal*_NonLiteral', '_NonLiteral*_Literal' ) );
            addRule( new TARuleFromString( '_Literal+_NonLiteral', '_NonLiteral+_Literal' ) );
            
            addRule( new TARuleFromString( '_Literal1+(_Literal2+_NonLiteral)', '_NonLiteral+(_Literal1+_Literal2)' ) );
            addRule( new TARuleFromString( '_Literal1+(_Literal2+_1)', '_1+(_Literal1+_Literal2)' ) );

            addRule( new TARuleFromString( '(_1*_2)+(_3*_2)', '(_1+_3)*_2' ) );
            addRule( new TARuleFromString( '(_2*_1)+(_2*_3)', '(_1+_3)*_2' ) );

            addRule( new TARuleFromString( '(_2*_1)+(_3*_2)', '(_1+_3)*_2' ) );
            addRule( new TARuleFromString( '(_1*_2)+(_2*_3)', '(_1+_3)*_2' ) );
            
            addRule( new TARuleFromString( '(_Literal * _1 ) / _Literal', '_1' ) );
            addRule( new TARuleFromString( '(_Literal1 * _1 ) / _Literal2', '(_Literal1 * _Literal2 ) / _1' ) );
            
            addRule( new TARuleFromString( '(_1+_2)+_3', '_1+(_2+_3)' ) );
            addRule( new TARuleFromString( '(_1*_2)*_3', '_1*(_2*_3)' ) );

            addRule( new TARuleFromString( '_1+(_1+_2)', '(2*_1)+_2' ) );

            addRule( new TARuleFromString( '_1+_2*_1', '(1+_2)*_1' ) );

            addRule( new TARuleFromString( '_literal1 * _NonLiteral = _literal2', '_literal2 / _literal1 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_literal1 + _NonLiteral = _literal2', '_literal2 - _literal1 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_literal1 - _NonLiteral = _literal2', '_literal1 - _literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_literal1 / _NonLiteral = _literal2', '_literal1 * _literal2 = _NonLiteral' ) );

ルールをファーストクラスの式にする

興味深い点：上記のルールは特殊な式であり、式パーサーによって正しく評価されるため、ユーザーは新しいルールを追加して、アプリケーションの書き換え機能を強化することもできます。

式の解析（またはより一般的な：言語）

Cocoa / OBjCアプリケーションの場合、Dave DeLongのDDMathParserは、数式を構文的に分析するのに最適な候補です。

他の言語の場合は、旧友のLex＆Yaccまたは新しいGNUBisonが役立つ可能性があります。

はるかに若く、すぐに使用できる構文ファイルの膨大なセットを備えたANTLRは、Javaに基づく最新のパーサジェネレータです。純粋にコマンドラインでの使用に加えて、ANTLRWorksは、 ANTLRベースのパーサーを構築およびデバッグするためのGUIフロントエンドを提供します。ANTLRは、 JAVA、C、Python、PHP、C＃などのさまざまなホスト言語の文法を生成します。現在、ActionScriptランタイムは壊れています。

式（または一般的な言語）をボトムアップで解析する方法を学びたい場合は、PascalとModulaの有名な発明者であるNiklaus Wirth（またはドイツ語の本版）からこの無料の本のテキストを提案します-2。

Answer 2

このタスクは非常に複雑になる可能性があります（最も単純な変換を除く）。本質的に、これは代数ソフトウェアが常に行うことです。

これがどのように行われるか（ルールベースの評価）、例えばMathematicaの場合、読みやすい紹介を見つけることができます。

Answer 3

CAS（数式処理システム）を構築したいと考えており、トピックが非常に広いため、それに特化した研究分野全体があります。つまり、おそらくSOよりもあなたの質問に答える本がいくつかあるということです。

一部のシステムは、最初に定数を減らすツリーを構築し、次にツリーを正規化された形式に変換してから、実績のある/既知の式の大規模なデータベースを使用して問題を他の形式に変換することを知っています。

Answer 4

私はあなたがそのような木を「ブルートフォース」しなければならないと信じています。

考えられる簡略化を説明するいくつかのルールを作成する必要があります。次に、ツリーをウォークスルーして、適用可能なルールを検索します。一部の簡略化は他の簡略化よりも単純な結果につながる可能性があるため、地下鉄の計画で最短ルートを見つけるために行うのと同様のことを行う必要があります。すべての可能性を試して、いくつかの品質基準で結果を並べ替えます。

このようなシナリオの数は有限であるため、演算子と変数のすべての組み合わせを試して、単純化ルールを自動的に検出し、ルールが以前に検出されていないこと、および実際に入力を単純化することを検証する遺伝的アルゴリズムを使用できる場合があります。 。

乗算は加算として表すことができるので、1つのルールはa --aがそれ自体をキャンセルすることかもしれません：2a-a = a + aa

もう1つのルールは、分数であるため、最初にすべての除算を乗算することです。例：

1/2 + 3/4すべての分数を検出し、各分数に他のすべての分数の両側の除数を掛けます

4/8 + 6/8次に、すべての要素が同じ除数を持つため、（4 + 6）/ 8=10/8に統合できます。

最後に、上部と下部の5/4の間で最大公約数を見つけます

ツリーに適用される戦略は、下の葉から上に向かって作業し、最初に各乗算を加算に変換することによって単純化することです。次に、分数のように各加算を単純化します

その間ずっと、ショートカットルールをもう一度チェックして、そのような単純化を発見します。ルールが適用されることを知るには、おそらくサブツリーのすべての順列を試す必要があります。たとえば、aaルールは-a+aにも適用されます。a+baがあるかもしれません。

いくつかの考え、それがあなたにいくつかのアイデアを与えることを願っています...

Answer 5

divide私の素朴なアプローチは、各関数（つまり、 ）の逆関数を持つある種のデータ構造を持つことmultiplyです。3を掛けてから、4で割るのは実際には逆ではないため、実際に逆であることを確認するために、さらにロジックが必要になることは明らかです。

これは原始的ですが、問題の最初のパスとしてはまともであり、質問で指摘した多くのケースを解決できると思います。

私はあなたの完全な解決策を見て、数学的な輝きを畏敬の念をもって見つめることを楽しみにしています:)

Answer 6

数学的には同じですが、コンピュータの算術では同じではない可能性があるため、実際には一般的にこれを行うことはできません。たとえば、-MAX_INTは未定義なので、-％a = / =％aです。同様に、フロートの場合、NaNとInfを適切に処理する必要があります。