21

キーが正規表現であり、文字列が辞書に対して検索される辞書(またはハッシュ、マップ、またはお気に入りの言語がそれを呼び出すもの)で検索を実行するための合理的に効率的な方法があるかどうかを把握しようとしていますキーのセット。例 (Python 構文):

>>> regex_dict = { re.compile(r'foo.') : 12, re.compile(r'^FileN.*$') : 35 }
>>> regex_dict['food']
12
>>> regex_dict['foot in my mouth']
12
>>> regex_dict['FileNotFoundException: file.x does not exist']
35

(明らかに、上記の例は Python で書かれたとおりには機能しませんが、それは私ができるようにしたいことです。)

これを実装する単純な方法を考えることができます。この方法では、辞書内のすべてのキーを反復処理し、渡された文字列をそれらに対して照合しようとしますが、ハッシュ マップの O(1) ルックアップ時間を失い、代わりに O(n) を使用します。ここで、n は辞書内のキーの数です。このディクショナリは非常に大きくなると予想されるため、これは大きな問題になる可能性があり、何度も何度も検索する必要があります (実際には、テキスト ファイルで読み取るすべての行に対して反復処理を行う必要があり、ファイルのサイズは数百メガバイトになる場合があります)。

O(n) 効率に頼らずにこれを達成する方法はありますか?

あるいは、データベースでこの種のルックアップを実行する方法を知っていれば、それも素晴らしいでしょう。

(どのプログラミング言語でも問題ありません。私は Python を使用していますが、ここでのデータ構造とアルゴリズムにもっと興味があります。)

複数の一致が可能であると誰かが指摘しましたが、それは完全に正しいです。理想的には、この状況では、すべての一致を含むリストまたはタプルを返したいと思います。しかし、私は最初の試合に落ち着くでしょう。

そのシナリオでは O(1) が可能であるとは思えません。ただし、O(n) 未満のもので解決します。また、基礎となるデータ構造は何でもかまいませんが、私が望む基本的な動作は、上で書いたものです: 文字列を検索し、正規表現キーに一致する値を返します。

4

19 に答える 19

4

「本物の」正規表現を使用している限り、これは間違いなく可能です。教科書の正規表現は、決定論的な有限状態マシンによって認識できるものです。これは主に、そこに後方参照を含めることができないことを意味します。

正規言語には「2 つの正規言語の和集合は正規である」という性質があります。つまり、1 つのステート マシンで一度に任意の数の正規表現を認識できるということです。ステート マシンは、式の数に対して O(1) 時間で実行されます (入力文字列の長さに対して O(n) 時間で実行されますが、ハッシュ テーブルもそうです)。

ステート マシンが完了すると、どの式が一致したかがわかります。そこから、O(1) 時間で簡単に値を検索できます。

于 2008-11-04T06:30:01.667 に答える
4

やりたいことは、xrdb でサポートされていることと非常によく似ています。ただし、グロビングのかなり最小限の概念しかサポートしていません。

内部的には、正規表現を文字トライとして格納することにより、正規言語のファミリよりも大きな正規言語ファミリを実装できます。

  • 単一の文字は単にトライ ノードになります。
  • . は、現在のトライ ノードのすべての子をカバーするワイルドカード挿入になります。
  • ※前項目の先頭のノードにトライするとバックリンクになります。
  • [az] 範囲は、範囲内の各文字の下に同じ後続の子ノードを繰り返し挿入します。注意してください。挿入/更新は多少コストがかかるかもしれませんが、検索は文字列のサイズに比例する可能性があります。いくつかのプレースホルダーを使用すると、一般的な組み合わせ爆発のケースを制御できます。
  • (foo)|(bar) ノードは複数の挿入になります

これは、文字列内の任意のポイントで発生する正規表現を処理しませんが、どちらかの側で .* を使用して正規表現をラップすることでモデル化できます。

Perl には、アイデアを探し出すことができる Text::Trie のようなモジュールがいくつかあります。(ちなみに、私はそれらの1つをいつでも書いたと思います)

于 2008-11-05T20:52:08.743 に答える
4

これは、どの言語の通常のハッシュ テーブルでも実行できません。キーを正規表現に一致させようとするか、別のデータ構造を使用して、キーセット全体を反復処理する必要があります。

解決しようとしている問題に適したデータ構造を選択する必要があります。任意の正規表現と照合する必要がある場合、適切な解決策がわかりません。使用する正規表現のクラスがより制限されている場合は、トライサフィックス ツリーなどのデータ構造を使用できる場合があります。

于 2008-11-03T21:44:41.197 に答える
4

一般的に、必要なのはレクサージェネレーターです。一連の正規表現を受け取り、それらを認識エンジンにコンパイルします。C を使用している場合は、「lex」が機能します。Python でレクサー ジェネレーターを使用したことはありませんが、選択できるものがいくつかあるようです。Google はPLYPyGgy、およびPyLexerを示しています。

正規表現がすべて何らかの形で互いに似ている場合、いくつかのショートカットを使用できる可能性があります。提案を行うには、解決しようとしている最終的な問題について詳しく知る必要があります。サンプルの正規表現とサンプル データを共有できますか?

また、ここで扱っている正規表現はいくつありますか? 単純なアプローチが機能しないと確信していますか? ロブ・パイクがかつて言ったように、「n が小さいとファンシーなアルゴリズムは遅く、n は通常小さい」。何千もの正規表現があり、何千もの正規表現があり、これがユーザーを待っているインタラクティブなアプリケーションでない限り、簡単な方法で正規表現をループするのが最善かもしれません。

于 2008-11-03T21:53:03.880 に答える
3

次はどうでしょうか。

class redict(dict):
def __init__(self, d):
    dict.__init__(self, d)

def __getitem__(self, regex):
    r = re.compile(regex)
    mkeys = filter(r.match, self.keys())
    for i in mkeys:
        yield dict.__getitem__(self, i)

これは基本的に Python の dict 型のサブクラスです。これにより、正規表現をキーとして指定でき、この正規表現に一致するすべてのキーの値が、yield を使用して反復可能な方法で返されます。

これにより、次のことができます。

>>> keys = ["a", "b", "c", "ab", "ce", "de"]
>>> vals = range(0,len(keys))
>>> red = redict(zip(keys, vals))
>>> for i in red[r"^.e$"]:
...     print i
... 
5
4
>>>
于 2009-05-03T01:18:14.650 に答える
3

次のような辞書があるとどうなりますか

regex_dict = { re.compile("foo.*"): 5, re.compile("f.*"): 6 }

この場合regex_dict["food"]、正当に 5 または 6 を返すことができます。

その問題を無視しても、正規表現モジュールでこれを効率的に行う方法はおそらくないでしょう。代わりに、内部有向グラフまたはツリー構造が必要になります。

于 2008-11-03T21:46:56.810 に答える
3

キーを単一のコンパイル済み正規表現に結合することにより、これを行う効率的な方法を次に示します。そのため、キー パターンをループする必要はありません。を悪用して、lastindexどのキーが一致したかを調べます。(残念なことに、regexp ライブラリでは、正規表現がコンパイルされる DFA の端末状態にタグを付けることはできません。さもなければ、これはあまりハックされません。)

式は 1 回コンパイルされ、順次検索する必要のない高速マッチャーが生成されます。一般的なプレフィックスは DFA で一緒にコンパイルされるため、他の提案された解決策とは異なり、キーの各文字は 1 回だけ照合されます。キースペース用のミニレクサーを効果的にコンパイルしています。

このマップは、正規表現を再コンパイルしないと拡張できません (新しいキーを定義できません) が、状況によっては便利です。

# Regular expression map
# Abuses match.lastindex to figure out which key was matched
# (i.e. to emulate extracting the terminal state of the DFA of the regexp engine)
# Mostly for amusement.
# Richard Brooksby, Ravenbrook Limited, 2013-06-01

import re

class ReMap(object):

    def __init__(self, items):
        if not items:
            items = [(r'epsilon^', None)] # Match nothing
        key_patterns = []
        self.lookup = {}
        index = 1
        for key, value in items:
            # Ensure there are no capturing parens in the key, because
            # that would mess up match.lastindex
            key_patterns.append('(' + re.sub(r'\((?!\?:)', '(?:', key) + ')')
            self.lookup[index] = value
            index += 1
        self.keys_re = re.compile('|'.join(key_patterns))

    def __getitem__(self, key):
        m = self.keys_re.match(key)
        if m:
            return self.lookup[m.lastindex]
        raise KeyError(key)

if __name__ == '__main__':
    remap = ReMap([(r'foo.', 12), (r'FileN.*', 35)])
    print remap['food']
    print remap['foot in my mouth']
    print remap['FileNotFoundException: file.x does not exist']
于 2013-06-01T18:20:58.337 に答える
2

このTie::Hash::Regexだけを行う Perl モジュールがあります。

use Tie::Hash::Regex;
my %h;

tie %h, 'Tie::Hash::Regex';

$h{key}   = 'value';
$h{key2}  = 'another value';
$h{stuff} = 'something else';

print $h{key};  # prints 'value'
print $h{2};    # prints 'another value'
print $h{'^s'}; # prints 'something else'

print tied(%h)->FETCH(k); # prints 'value' and 'another value'

delete $h{k};   # deletes $h{key} and $h{key2};
于 2008-11-04T04:31:23.857 に答える
2

@rptb1 re.groups を使用してグループをカウントできるため、グループのキャプチャを回避する必要はありません。このような:

# Regular expression map
# Abuses match.lastindex to figure out which key was matched
# (i.e. to emulate extracting the terminal state of the DFA of the regexp engine)
# Mostly for amusement.
# Richard Brooksby, Ravenbrook Limited, 2013-06-01

import re

class ReMap(object):
    def __init__(self, items):
        if not items:
            items = [(r'epsilon^', None)] # Match nothing
        self.re = re.compile('|'.join('('+k+')' for (k,v) in items))
        self.lookup = {}
        index = 1
        for key, value in items:
            self.lookup[index] = value
            index += re.compile(key).groups + 1

    def __getitem__(self, key):
        m = self.re.match(key)
        if m:
            return self.lookup[m.lastindex]
        raise KeyError(key)

def test():
    remap = ReMap([(r'foo.', 12),
                   (r'.*([0-9]+)', 99),
                   (r'FileN.*', 35),
                   ])
    print remap['food']
    print remap['foot in my mouth']
    print remap['FileNotFoundException: file.x does not exist']
    print remap['there were 99 trombones']
    print remap['food costs $18']
    print remap['bar']

if __name__ == '__main__':
    test()

悲しいことに、実際に正規表現をマシンコードにコンパイルする RE エンジンはほとんどありませんが、特に難しくはありません。誰かが本当に優れた RE JIT ライブラリを作成するのを待っていると、桁違いのパフォーマンスの改善があるのではないかと思います。

于 2013-06-01T23:32:46.203 に答える
1

この問題の特殊なケースは、演繹的なデータベースを中心とした 70 年代の AI 言語で発生しました。これらのデータベースのキーは、* または | を使用しない正規表現のように、変数を含むパターンである可能性があります。オペレーター。彼らは、トライ構造の派手な拡張をインデックスに使用する傾向がありました。一般的な考え方については、Norvig's Paradigms of AI Programmingの krep*.lisp を参照してください。

于 2008-11-04T05:02:57.570 に答える
1

可能な入力のセットが小さい場合は、2 番目の dict に表示される一致をキャッシュし、キャッシュされた値に対して O(1) を取得できます。

可能な入力のセットが大きすぎてキャッシュできないが、無限でもない場合は、最後の N 個の一致をキャッシュに保持することができます (Google で「LRU マップ」を確認してください - 最も最近使用されていません)。

これができない場合は、接頭辞などをチェックして、試行する正規表現の数を減らすことができます。

于 2008-11-04T12:39:42.000 に答える
1

プロジェクト用にこの正確なデータ構造を一度作成しました。あなたが示唆したように、私は単純にそれを実装しました。データのサイズに応じて、実行できる場合と実行できない場合がある、2 つの非常に役立つ最適化を行いました。

  • ハッシュルックアップのメモ化
  • メモ化テーブルのプレシード (これを何と呼べばよいかわかりません... キャッシュをウォームアップしますか?)

複数のキーが入力に一致する問題を回避するために、各正規表現キーに優先順位を付け、最も高い優先順位が使用されました。

于 2008-11-06T05:55:42.780 に答える
1

他の回答者が指摘しているように、一定時間でハッシュ テーブルを使用してこれを行うことはできません。

役立つかもしれない 1 つの近似は、 「n-gram」と呼ばれる手法を使用することです。単語の n 文字のチャンクから単語全体への転置インデックスを作成します。パターンが与えられたら、それを n 文字のチャンクに分割し、インデックスを使用して、一致する単語のスコア付きリストを計算します。

概算を受け入れることができない場合でも、ほとんどの場合、これにより正確なフィルタリング メカニズムが提供されるため、すべてのキーに正規表現を適用する必要はありません。

于 2008-11-03T21:54:01.337 に答える
0

OK、私は非常によく似た要件を持っています。異なる構文の行がたくさんあります。基本的には、スマートカード形式のプロセスで使用するための行とコードを含む行、およびキーと秘密コードの記述子行を示しています。いずれにせよ、「モデル」パターン/アクションは、多くの行を認識して処理するための獣のアプローチだと思います。という名前のアセンブリを開発するために for を
使用しています。このライブラリのコアは、基本的に を含む lex_rule クラスです。C++/CLILanguageProcessor.dll

  • 正規表現メンバー
  • イベントメンバー

DynamicMethodコンストラクターは正規表現文字列をロードし、Emitを使用してオンザフライでイベントを構築するために必要なコードを呼び出しますReflexion。また、アセンブリには、メタやオブジェクトなどの他のクラスが存在し、パブリッシャーの単純な名前でオブジェクトをインスタンス化して構築します。受信者クラス、受信者クラスは、一致した各ルールのアクション ハンドラーを提供します。

遅れて 、配列から定義をロードして実行するfasterlex_engineDictionary を構築するという名前のクラスがあります。<Regex, action_delegate>

プロジェクトは進んでいますが、今日もまだ構築中です。次のような正規表現を使用して辞書を直接検索するメカニズムを使用して、すべてのペアの foreach 行入力への順次アクセスを囲む実行のパフォーマンスを向上させようとします。

map_rule[gcnew Regex("[a-zA-Z]")];

ここに、私のコードのいくつかのセグメントがあります:

public ref class lex_rule: ILexRule
{
private:
    Exception           ^m_exception;
    Regex               ^m_pattern;

    //BACKSTORAGE delegates, esto me lo aprendi asiendo la huella.net de m*e*da JEJE
    yy_lexical_action   ^m_yy_lexical_action; 
    yy_user_action      ^m_yy_user_action;

public: 
    virtual property    String ^short_id; 
private:
    void init(String ^_short_id, String ^well_formed_regex);
public:

    lex_rule();
    lex_rule(String ^_short_id,String ^well_formed_regex);
    virtual event    yy_lexical_action ^YY_RULE_MATCHED
    {
        virtual void add(yy_lexical_action ^_delegateHandle)
        {
            if(nullptr==m_yy_lexical_action)
                m_yy_lexical_action=_delegateHandle;
        }
        virtual void remove(yy_lexical_action ^)
        {
            m_yy_lexical_action=nullptr;
        }

        virtual long raise(String ^id_rule, String ^input_string, String ^match_string, int index) 
        {
            long lReturn=-1L;
            if(m_yy_lexical_action)
                lReturn=m_yy_lexical_action(id_rule,input_string, match_string, index);
            return lReturn;
        }
    }
};

多くのパターン/アクションのペアを実行する高速なlex_engineクラス:

public ref class fasterlex_engine 
{
private: 
    Dictionary<String^,ILexRule^> ^m_map_rules;
public:
    fasterlex_engine();
    fasterlex_engine(array<String ^,2>^defs);
    Dictionary<String ^,Exception ^> ^load_definitions(array<String ^,2> ^defs);
    void run();
};

そして、このトピックを飾るために..私のcppファイルのいくつかのコード:

このコードは、パラメーター サインによってコンストラクター呼び出し元を作成します

inline Exception ^object::builder(ConstructorInfo ^target, array<Type^> ^args)
{
try
{
    DynamicMethod ^dm=gcnew DynamicMethod(
        "dyna_method_by_totem_motorist",
        Object::typeid,
        args,
        target->DeclaringType);
    ILGenerator ^il=dm->GetILGenerator();
    il->Emit(OpCodes::Ldarg_0);
    il->Emit(OpCodes::Call,Object::typeid->GetConstructor(Type::EmptyTypes)); //invoca a constructor base
    il->Emit(OpCodes::Ldarg_0);
    il->Emit(OpCodes::Ldarg_1);
    il->Emit(OpCodes::Newobj, target); //NewObj crea el objeto e invoca al constructor definido en target
    il->Emit(OpCodes::Ret);
    method_handler=(method_invoker ^) dm->CreateDelegate(method_invoker::typeid);
}
catch (Exception ^e)
{
    return  e;
}
return nullptr;

}

このコードは、入力文字列の一致によって発生したコールバックを処理するために、任意のハンドラー関数 (静的または非静的) をアタッチします。

Delegate ^connection_point::hook(String ^receiver_namespace,String ^receiver_class_name, String ^handler_name)
{
Delegate ^d=nullptr;
if(connection_point::waitfor_hook<=m_state) // si es 0,1,2 o mas => intenta hookear
{ 
    try 
    {
        Type ^tmp=meta::_class(receiver_namespace+"."+receiver_class_name);
        m_handler=tmp->GetMethod(handler_name);
        m_receiver_object=Activator::CreateInstance(tmp,false); 

        d=m_handler->IsStatic?
            Delegate::CreateDelegate(m_tdelegate,m_handler):
            Delegate::CreateDelegate(m_tdelegate,m_receiver_object,m_handler);

        m_add_handler=m_connection_point->GetAddMethod();
        array<Object^> ^add_handler_args={d};
        m_add_handler->Invoke(m_publisher_object, add_handler_args);
        ++m_state;
        m_exception_flag=false;
    }
    catch(Exception ^e)
    {
        m_exception_flag=true;
        throw gcnew Exception(e->ToString()) ;
    }
}
return d;       
}

最後に、レクサーエンジンを呼び出すコード:

array<String ^,2> ^defs=gcnew array<String^,2>  {/*   shortID    pattern         namespc    clase           fun*/
                                                    {"LETRAS",  "[A-Za-z]+"     ,"prueba",  "manejador",    "procesa_directriz"},
                                                    {"INTS",    "[0-9]+"        ,"prueba",  "manejador",    "procesa_comentario"},
                                                    {"REM",     "--[^\\n]*"     ,"prueba",  "manejador",    "nullptr"}
                                                }; //[3,5]

//USO EL IDENTIFICADOR ESPECIAL "nullptr" para que el sistema asigne el proceso del evento a un default que realice nada
fasterlex_engine ^lex=gcnew fasterlex_engine();
Dictionary<String ^,Exception ^> ^map_error_list=lex->load_definitions(defs);
lex->run();
于 2011-04-29T17:50:33.013 に答える
0

この問題は正規表現とは何の関係もありません。ラムダの関数としてキーを持つ辞書でも同じ問題が発生します。したがって、あなたが直面している問題は、関数を分類して true を返すかどうかを判断する方法があり、f(x) は一般に事前にわかっていないため、検索の問題ではありません。

x の値が共通であると仮定して、分散プログラミングまたは回答セットのキャッシングが役立つ場合があります。

--DM

于 2012-04-17T11:51:38.903 に答える
0

それは、これらの正規表現がどのように見えるかに大きく依存します。.*' ' や ' 'などのほとんどすべてに一致する正規表現があまりなく\d+、その代わりに、ほとんどが単語やフレーズ、または 4 文字を超える固定パターン (' a*b*c' in^\d+a\*b\*c:\s+\w+など) を含む正規表現がある場合、例。何百万もの正規表現にうまくスケーリングするこの一般的なトリックを実行できます。

正規表現の逆索引を作成します (rabin-karp-hash('fixed pattern') -> 'fixed pattern' を含む正規表現のリスト)。次に、照合時に、Rabin-Karp ハッシュを使用してスライディング ハッシュを計算し、逆インデックスを検索して、一度に 1 文字ずつ進めます。これで、逆インデックスの非一致に対する O(1) ルックアップと、一致に対する合理的な O(k) 時間があります。k は、逆インデックスの正規表現のリストの平均の長さです。多くのアプリケーションでは、k は非常に小さい (10 未満) 場合があります。転置インデックスの品質 (偽陽性は k が大きいことを意味し、偽陰性は一致を逃したことを意味します) は、インデクサーが正規表現構文をどれだけ理解しているかによって異なります。正規表現が人間の専門家によって生成された場合、含まれている固定パターンのヒントも提供できます。

于 2008-11-04T01:57:30.657 に答える
0

理論上もありえないと思います。複数の正規表現に一致する文字列を渡すとどうなりますか。

たとえば、誰かが次のことをしたらどうなるでしょうか。

>>> regex_dict['FileNfoo']

そのようなものが O(1) である可能性はありますか?

于 2008-11-03T21:44:49.247 に答える
0

基本的な仮定には欠陥があると思います。ハッシュを正規表現にマップすることはできません。

于 2008-11-03T21:44:21.870 に答える
0

検索式を "|" で区切られた 1 つの大きな正規表現に連結することで、正規表現コンパイラにほとんどの作業を行わせることができる場合があります。このような場合、巧妙な正規表現コンパイラは代替案の共通点を検索し、単純にそれぞれを順番にチェックするよりも効率的な検索戦略を考案する可能性があります。しかし、それを行うコンパイラがあるかどうかはわかりません。

于 2008-11-04T00:13:40.163 に答える