Selbstanpassender Regex [geschlossen]

15

Schreiben Sie einen nicht trivialen regulären Ausdruck, der mit sich selbst übereinstimmt.

Entspricht beispielsweise #.*$einem Kommentar außerhalb eines Strings in Python bis zum Zeilenende und entspricht sich auch in der regulären Perl-Syntax.

Regeln :

  • Der reguläre Ausdruck muss etwas Nützliches oder Praktisches tun.
  • Geben Sie an, welche Regex-Syntax Sie verwenden (z. B. Perl oder POSIX).
  • Gewinner ist die Antwort mit der höchsten Bewertung.
  • Seien Sie kreativ!
Casey Kuball
quelle
6
Vor einiger Zeit gab es eine Frage zu SO, ob es eine Regex gibt, die mit gültigen Regexen übereinstimmt: stackoverflow.com/questions/172303/…
Patrick Oscity
5
Definieren Sie nicht-trivial. Ich meine, OK, Awäre trivial, aber wo ziehst du die Grenze? Und mit "Self-Matching" meinen Sie, dass es nur sich selbst entsprechen kann, oder darf es auch anderen Zeichenfolgen entsprechen? Würde sich .qualifizieren?
Mr Lister
1
@padde, das eigentlich kein regulärer Ausdruck war, weil die Grammatik, die den regulären Ausdruck beschreibt, kontextfrei ist.
FUZxxl
1
@FUZxxl ja, das stimmt, aber man könnte immer noch einen regulären Ausdruck schreiben, der mit anderen regulären Ausdrücken übereinstimmt, aber die Gültigkeit der übereinstimmenden regulären Ausdrücke spielt keine Rolle.
Patrick Oscity
1
@padde Nun, was ist dann ein ungültiger regulärer Ausdruck? Ein ungültiger regulärer Ausdruck ist offensichtlich kein regulärer Ausdruck. Sie sagen also im Wesentlichen: "Ja, das ist wahr, aber man könnte immer noch einen regulären Ausdruck schreiben, der mit anderen regulären Ausdrücken übereinstimmt, aber es ist egal, ob der passende reguläre Ausdruck wirklich ein regulärer Ausdruck ist" (sic!)
FUZxxl

Antworten:

11

PYTHON

Unten sehen Sie einen selbstanpassenden Regex-Generator. Sie stellen zwei Listen zur Verfügung, eine enthält Trainingsdaten, mit denen der Regex übereinstimmen soll (zusätzlich zu der eigenen), die andere enthält Trainingsdaten, mit denen der Regex NICHT übereinstimmen soll:

from random import choice, randrange
import re
from itertools import zip_longest, chain, islice
from operator import itemgetter

CHAR_SET = [chr(i) for i in range(128)] + [r"\\", r"\d", r"\D",
                                           r"\w", r"\W", r"\s",
                                           r"\S", r"?:", r"\1",
                                           r"\2", r"\A", r"\b",
                                           r"\B", r"\Z", r"\.",
                                           r"\[", r"\]", r"\(",
                                           r"\)", r"\{", r"\}",
                                           r"\+", r"\|", r"\?",
                                           r"\*"]

CHAR_SAMPLE = []
BREAKPOINT = re.compile(
    r"""
    \(.*?\)|
    \[.*?\]|
    \{.*?\}|
    \w+(?=[\(\[\{])?|
    \S+?|
    \.\*\??|
    \.\+\??|
    \.\?\??|
    \\.|
    .*?
    """,
    re.VERBOSE)

MATCH_BRACKETS = {'(': ')', '[': ']', '{': '}'}
CLOSE_BRACKETS = {')', ']', '}'}
REGEX_SEEDER = [
    r".*?",
    r"(?:.*?)",
    r"\w|\s",
    r"(?<.*?)",
    r"(?=.*?)",
    r"(?!.*?)",
    r"(?<=.*?)",
    r"(?<!.*?)",
    ]

LEN_LIMIT = 100

def distribute(distribution):
    global CHAR_SAMPLE
    for item in CHAR_SET:
        if item in distribution:
            CHAR_SAMPLE.extend([item] * distribution[item])
        else:
            CHAR_SAMPLE.append(item)

def rand_index(seq, stop=None):
    if stop is None:
        stop = len(seq)
    try:
        return randrange(0, stop)
    except ValueError:
        return 0

def rand_slice(seq):
    try:
        start = randrange(0, len(seq))
        stop = randrange(start, len(seq))
        return slice(start, stop)
    except ValueError:
        return slice(0,  0)


#Mutation Functions

def replace(seq):
    seq[rand_index(seq)] = choice(CHAR_SAMPLE)

def delete(seq):
    del seq[rand_index(seq)]

def insert(seq):
    seq.insert(rand_index(seq, len(seq) + 1), choice(CHAR_SAMPLE))

def duplicate(seq):
    source = rand_slice(seq)
    seq[source.stop: source.stop] = seq[source]

def swap(seq):
    if len(seq) < 2: return
    a = rand_index(seq, len(seq) - 1)
    seq[a], seq[a + 1] = seq[a + 1], seq[a]

dummy = lambda seq: None

MUTATE = (
    replace,
    delete,
    insert,
    duplicate,
    swap,
    dummy,
    dummy,
    )

def repair_brackets(seq):
    """Attempts to lower the percentage of invalid regexes by
    matching orphaned brackets"""

    p_stack, new_seq = [], []
    for item in seq:
        if item in MATCH_BRACKETS:
            p_stack.append(item)
        elif item in CLOSE_BRACKETS:
            while p_stack and MATCH_BRACKETS[p_stack[-1]] != item:
                new_seq.append(MATCH_BRACKETS[p_stack[-1]])
                p_stack.pop()
            if not p_stack:
                continue
            else:
                p_stack.pop()
        new_seq.append(item)
    while p_stack:
        new_seq.append(MATCH_BRACKETS[p_stack.pop()])
    return new_seq

def compress(seq):
    new_seq = [seq[0]]
    last_match = seq[0]
    repeat = 1
    for item in islice(seq, 1, len(seq)):
        if item == last_match:
            repeat += 1
        else:
            if repeat > 1:
                new_seq.extend(list("{{{0}}}".format(repeat)))
            new_seq.append(item)
            last_match = item
            repeat = 1
    else:
        if repeat > 1:
            new_seq.extend(list("{{{0}}}".format(repeat)))
    return new_seq


def mutate(seq):
    """Random in-place mutation of sequence"""
    if len(seq) > LEN_LIMIT:
        seq[:] = seq[:LEN_LIMIT]
    c = choice(MUTATE)
    c(seq)

def crossover(seqA, seqB):
    """Recombination of two sequences at optimal breakpoints
    along each regex strand"""

    bpA = [item.start() for item in BREAKPOINT.finditer(''.join(seqA))]
    bpB = [item.start() for item in BREAKPOINT.finditer(''.join(seqA))]
    slObjA = (slice(*item) for item in zip(bpA, bpA[1:]))
    slObjB = (slice(*item) for item in zip(bpB, bpB[1:]))
    slices = zip_longest(
        (seqA[item] for item in slObjA),
        (seqB[item] for item in slObjB),
        fillvalue=[]
        )
    recombinant = (choice(item) for item in slices)
    return list(chain.from_iterable(recombinant))

#Fitness testing

def match_percentage(match):
    """Calculates the percentage a text actually matched
    by a regular expression"""

    if match and match.endpos:
        return (match.end() - match.start()) / match.endpos
    else:
        return 0.001

def fitness_test(seq, pos_matches, neg_matches):
    """Scoring algorithm to determine regex fitness"""

    try:
        self_str = ''.join(seq)
        regex = re.compile(self_str)
    except (re.error, IndexError):
        seq[:] = repair_brackets(seq)
        try:
            self_str = ''.join(seq)
            regex = re.compile(self_str)
        except (re.error, IndexError):
            return 0.001

    pos_score = sum(match_percentage(regex.search(item))
                    for item in pos_matches) / len(pos_matches) / 3

    neg_score = (1 - sum(match_percentage(regex.search(item))
                    for item in neg_matches) / len(neg_matches)) / 3

    self_score = match_percentage(regex.search(self_str)) / 3

    return pos_score + self_score + neg_score

#Population Management

def generate_pop(pos_matches, neg_matches, pop_size):
    sources = (pos_matches, REGEX_SEEDER)
    return [crossover(
        choice(choice(sources)), choice(choice(sources))
        ) for i in range(pop_size)]

def glean_pop(population, cutoff, fit_test, ft_args=()):
    scores = (fit_test(bug, *ft_args) for bug in population)
    ranked = sorted(zip(population, scores), key=itemgetter(1), reverse=True)
    maxItem = ranked[0]
    new_pop = next(zip(*ranked))[:cutoff]
    return maxItem, new_pop

def repopulate(population, pop_size):
    cutoff = len(population)
    for i in range(pop_size // cutoff):
        population.extend([crossover(choice(population), choice(population))
                           for i in range(cutoff)])
    population.extend([population[i][:] for i in range(pop_size - len(population))])

#Simulator
def simulate(pos_matches, neg_matches, pop_size=50, cutoff=10, threshold=1.0):
    population = generate_pop(pos_matches, neg_matches, pop_size)
    while True:
        for bug in population:
            mutate(bug)

        #Scoring step
        max_item, population = glean_pop(
            population,
            cutoff,
            fitness_test,
            (pos_matches, neg_matches)
            )

        #Exit condition:
        max_regex, max_score = max_item
        if max_score >= threshold:
            return max_score, max_regex
        """
        print(max_score, ''.join(max_regex))
        input("next?")"""

        #Repopulation Step:
        population = list(population)
        repopulate(population, pop_size)
Joel Cornett
quelle
1
Ist das Python?
Griffin
1
@JoelCornett Das Schreiben meiner eigenen simulateFunktion ist Teil der Verwendung? Ihre simulateFunktion verwendet Argument 2 nicht.
Casey Kuball
1
@Darthfett: Nein, das ist ein Beispiel dafür, wie Sie die Funktion aufrufen würden. Ich habe Variablennamen verwendet, die den (hypothetischen) Inhalt beschreiben. Mein Fehler bei Parameter 2 war ein Tippfehler. no_matchsoll umbenannt werden no_match_list. Bearbeitet
Joel Cornett
1
Warum rufen Sie auf population = generate_pop(pos_matches, neg_matches, pop_size), aber die generate_popFunktion verwendet den neg_matchesParameter nie ? Können Sie auch ein Beispiel für den Aufruf der Funktion beifügen? Könnte ich es so nennen simulate(["Hello","World","world"], ["woah","bad","dont match"])?
mbomb007
1
Hey, es ist ein paar Jahre her, seit ich das geschrieben habe. Wenn Sie den Code einfach durchlesen, ohne ihn zu testen, können Sie die simulate()Funktion wie beschrieben aufrufen . Und ja, Sie haben Recht: Ich verwende die negativen Daten nicht zur Generierung der ursprünglichen Grundgesamtheit.
Joel Cornett
5

Regulärer JavaScript-Ausdruck, der ähnlichen Elementen entspricht.

/^\/\^\\\/\\\^[\\\[\]\/\^\${},\dd]{34}$/

Sie können es so testen:

(function test() {
    var re =/^\/\^\\\/\\\^[\\\[\]\/\^\${},\dd]{34}$/;
    var m  =/=([^;]+)/.exec(test)[1];
    return re.exec(m);
})();
Ry-
quelle
1
Was ist "so was"? Ist das in irgendeiner Weise praktisch oder nützlich?
Casey Kuball
2
@Darthfett: Es stimmt mit ähnlichen regulären Ausdrücken überein, die versuchen, sich selbst und diesen regulären Ausdruck abzugleichen. Nein, es ist in keiner Weise praktisch oder nützlich, aber der einzig mögliche praktische oder nützliche, aber auch interessante reguläre Ausdruck, der mit sich selbst übereinstimmt, ist ein regulärer Ausdruck, der mit regulären Ausdrücken übereinstimmt. Welches wurde getan.
Ry