3

小文字の化学式のあいまいさを解決しようとしています。一部の要素名は他の要素名のサブストリングであり、それらはすべて一緒に実行されるため、同じパターンに対して複数のグローバル一致が存在する可能性があります。

/^((h)|(s)|(hg)|(ga)|(as))+$/文字列に対する正規表現を検討しますhgas。一致する可能性のあるものは2つあります。hg, asおよびh, s, ga（入力と比較して順序が狂っていますが、問題はありません）。明らかに、すべての可能なシンボルの正規表現は長くなりますが、この例は簡単にするために行われました。

正規表現の強力な先読みと後読みにより、非常に長い文字列でさえこのパターンに一致するか、文字の可能な順列がないかを最終的に判断できます。一致する可能性のあるすべての順列を熱心に試します。たとえば、文字列の最後に残り物が当たった場合は、g戻って別の組み合わせを再試行します。

正規表現、またはある種の拡張機能を備えた言語を探しています。これにより、一致が見つかった後も検索を続けることができます。この場合は、検索h, s, gaも同様hg, asです。

この問題に対する正規表現の複雑な先読み機能と後読み機能を再構築することは、特に最終的な正規表現に各記号の後に\ d *が含まれていることを考えると、合理的な解決策とは思えません。

正規表現の順序を逆にして、追加のマッピングを見つけることを考えまし/^((as)|(ga)|(hg)|(s)|(h))+$/たが、多くても1つの追加の一致しか見つかりません。また、正規表現の理論的背景がなく、試してみるのが合理的かどうかもわかりません。

既存の正規表現を使用してサンプルページを作成しました。この正規表現は、指定された小文字の文字列に一致するものを1つまたは0つ見つけて、適切に大文字で（順序が狂って）返します。マッチングでは最初の100個の化学記号を使用します。

http://www.ptable.com/Script/lowercase_formula.php?formula=hgas

tl; dr：文字列内の0または1つの可能な化学式の順列に一致する正規表現があります。複数の一致を見つけるにはどうすればよいですか？

4

4 に答える 4

3

私はこの答えが（アプローチのように）トピックから外れているかもしれないことをよく知っていますが、それは非常に興味深いと思います、そしてそれはOPの問題を解決します。

新しい言語（Prolog）を習得してもかまわない場合は、考えられるすべての組み合わせを生成するのに役立つ可能性があります。

name(X) :- member(X, ['h', 's', 'hg', 'ga', 'as']).

parse_([], []).
parse_(InList, [HeadAtom | OutTail]) :-
    atom_chars(InAtom, InList),
    name(HeadAtom),
    atom_concat(HeadAtom, TailAtom, InAtom),
    atom_chars(TailAtom, TailList),
    parse_(TailList, OutTail).

parse(In, Out) :- atom_chars(In, List), parse_(List, Out).

サンプル実行：

?- parse('hgas', Out).
Out = [h, ga, s] ;
Out = [hg, as] ;
false.

数値の処理を含む改善されたバージョンは、少し長くなっています。

isName(X) :- member(X, ['h', 's', 'hg', 'ga', 'as', 'o', 'c']).

% Collect all numbers, since it will not be part of element name.
collect([],[],[]).
collect([H|T], [], [H|T]) :-
    \+ char_type(H, digit), !.
collect([H|T], [H|OT], L) :-
    char_type(H, digit), !, collect(T, OT, L).

parse_([], []).
parse_(InputChars, [Token | RestTokens]) :-
    atom_chars(InputAtom, InputChars),
    isName(Token),
    atom_concat(Token, TailAtom, InputAtom),
    atom_chars(TailAtom, TailChars),
    parse_(TailChars, RestTokens).

parse_(InputChars, [Token | RestTokens]) :-
    InputChars = [H|_], char_type(H, digit),
    collect(InputChars, NumberChars, TailChars),
    atom_chars(Token, NumberChars),
    parse_(TailChars, RestTokens).

parse(In, Out) :- atom_chars(In, List), parse_(List, Out).

サンプル実行：

?- parse('hgassc20h245o', X).
X = [h, ga, s, s, c, '20', h, '245', o] ;
X = [hg, as, s, c, '20', h, '245', o] ;
false.

?- parse('h2so4', X).
X = [h, '2', s, o, '4'] ;
false.

?- parse('hgas', X).
X = [h, ga, s] ;
X = [hg, as] ;
false.
于 2012-09-19T20:08:28.463 に答える
1

これを行う一般化された正規表現ライブラリが見つからない理由は、すべての正規表現でこれを行うことができないためです。終了しない正規表現があります。

あなたの例で、用語のリストに空の文字列を追加したところを想像してみてください。

'hgas'は次のようになります。

['hg', 'as']
['hg', '', 'as']
['hg', '', '', 'as']

あなたはおそらくあなた自身を転がす必要があるでしょう。

疑似コードの場合：

def findall(term, possible):
    out = []

    # for all the terms
    for pos in possible:

        # if it is a candidate
        if term.startswith(pos):

            # combine it with all possible endings
            for combo in findall(term.removefrombegining(pos), possible):
                newCombo = combo.prepend(out)
                out.append(newCombo)
    return out


findall('hgas', ['h', 'as', ...])

上記は指数関数的に実行されるため、動的計画法はこれが指数関数的に大きな問題ではない方法になります。勝利のためのメモ化。

注目に値する最後のことは、上記のコードが完全に一致することをチェックしないことです。

すなわち。'hga'は可能性として['hg']を返す可能性があります。

私の教授が愛情を込めて言うように、私は実際のコーディング、記憶、そしてこの最後のしゃっくりを「読者への練習」に任せます

于 2012-09-19T19:44:37.200 に答える
0

正規表現は使用しないでください。あなたが言うように、正規表現は1つの要素にのみ一致します。代わりに、文字列のすべての可能な「意味」を見つける必要があります。各要素の長さが1〜2文字であるという事実を考えると、私はこのアルゴリズムを使用します（擬似コードを許します）。

string[][] results;



void formulas(string[] elements, string formula){
    string[] elements2=elements;


    if(checkSymbol(formula.substring(0,1))){
        elements.append(formula.substring(0,1));
        if(formula.length-1 ==0){
            results.append(elements);
        } else {
            formulas(elements,formula.substring(1,formula.length);
        }
    }
    if(checkSymbol(formula.substring(0,2))){
        elements2.append(formula.substring(0,2));
        if(formula.length-2 ==0){
            results.append(elements2);
        } else {
            formulas(elements2,formula.substring(2,formula.length);
        }
    }


}

bool checkSymbol(string symbol){
    // verifies if symbol is the name of an element
}

入力"hgas"（最初に深さ優先）

checkSymbol(formula.substring(0,1))最初のステップ： "h"

elements2 = [h]

再帰呼び出し、if(checkSymbol(formula.substring(0,1))) false

次にテストしますga=>true

elements2 = [h, ga]

3番目の再帰呼び出し

test s、checksymboltrueを返し、要素は[h, ga, s]。サブストリングの長さは0であるため、結果に最初の配列を追加します。[h, ga, s]

--最初のステップの2番目の「ブランチ」に戻りましょう

テストでは、それも要素であるcheckSymbol(formula.substring(0,2)ことがわかります"hg"

elements2 = [hg]

次に、formulas([hg],"as")

失敗のテスト"a"（要素ではありません）と"as"動作のテスト、長さは完全に消費され、結果[hg,as]はに追加されますresults[]

このアルゴリズムは、最悪の場合、O（n ^ 2）時間で実行されるはずです。ここで、nは文字列の長さです。

于 2012-09-19T20:18:47.423 に答える
0

これは正規表現の仕事ではありません。ステートマシンのようなものが必要です。

既知のすべての記号をポップアウトし、存在しない場合は停止して続行する文字列を解析する必要があります。文字列全体が1つのブランチで消費される場合は、可能性があります。

PHPでは、次のようになります。

<?php
    $Elements = array('h','he','li','s','ga','hg','as',
         // "...and there may be many others, but they haven't been discovered".
    );

    function check($string, $found = array(), $path = '')
    {
        GLOBAL $Elements, $calls;
        $calls++;
        if ('' == $string)
        {
            if (!empty($path))
                $found[] = $path;
            return $found;
        }
        $es = array_unique(array(
                  substr($string, 0, 1), // Element of 1 letter ("H")
                  substr($string, 0, 2), // Element of 2 letter ("He")
        ));
        foreach($es as $e)
            if (in_array($e, $Elements))
                    $found  = check(substr($string, strlen($e)), $found, $path.$e.',');
        return $found;
    }

    print_r(check('hgas'));
    print "in $calls calls.\n";
?>
于 2012-09-19T20:32:31.047 に答える