以编程方式从字符串派生正则表达式

I would like to input a string and return a regular expression that can be used to describe the string's structure. The regex will be used to find more strings of the same structure as the first.

我想输入一个字符串并返回一个可用于描述字符串结构的正则表达式。正则表达式将用于查找与第一个相同结构的更多字符串。

This is intentionally ambiguous because I will certainly miss a case that someone in the SO community will catch.

这是故意模棱两可的，因为我肯定会错过SO社区中的某个人会抓住的案例。

Please post any and all possible ways to do this.

请发布任何和所有可能的方法来执行此操作。

4 个解决方案

#1

The trivial answer, and probably not what you want, is: return the input string (with regex special characters escaped). That is always a regular expression that matches the string.

琐碎的答案，可能不是你想要的，是：返回输入字符串（带有正则表达式特殊字符转义）。这始终是匹配字符串的正则表达式。

If you wish certain structures to be identified, you have to provide more information about the kind of structures you wish to have identified. Without that information, the problem is stated in an ambiguous way and there are many possible solutions. For instance, the input string 'aba' can be described as

如果您希望识别某些结构，则必须提供有关您希望识别的结构类型的更多信息。没有这些信息，问题就会以模棱两可的方式陈述，并且有许多可能的解决方案。例如，输入字符串'aba'可以描述为

'aba'

'ABA'

'aba*'

'ABA *'

'aba?'

'ABA？'

'ab\w'

'AB \ W'

'\w{3}'

'\瓦特{3}'

'(.)b\1'

'（）。B \ 1'

etc.

等等

#2

Sorry for the length of this. I took the premise of this as a little challenge and came up with a proof of concept in Ruby.

对不起这个长度。我把这个作为一个小挑战的前提，并在Ruby中提出了一个概念证明。

I worked on the assumption that you could supply a number of strings that should match the regular expression (HITS) and a number that should fail to match (MISSES).

我的假设是你可以提供一些与正则表达式（HITS）匹配的字符串和一个不匹配的数字（MISSES）。

I based the code on a naive implementation of a genetic algorith. See the notes at the bottom for my thoughts on the success, or otherwise, of this approach.

我将代码基于遗传算法的简单实现。请参阅底部的注释，了解我对此方法成功与否的看法。

LOOP_COUNT = 100

class Attempt

  # let's try email
  HITS    = %w[[e-mail] [e-mail] [e-mail] [e-mail] [e-mail] [e-mail] [e-mail] [e-mail] [e-mail] [e-mail]]
  MISSES  = %w[j@j j@j@.com j.com @domain.com nochance eric@google. [e-mail]. username-at-domain-dot-com linux.org eff.org microsoft.com sjobs.apple.com www.apple.com]

  # odd mixture of numbers and letters, designed to confuse
  # HITS = %w[a123 a999 a600 a545 a100 b001 b847 a928 c203]
  # MISSES = %w[abc def ghi jkl mno pqr stu vwx xyz h234 k987]

  # consonants versus vowels
  # HITS = %w[bcd cdb fgh ghf jkl klj mnp npm qrs srq tvw vwt xzb bzx]
  # MISSES = %w[aei oyu oio euu uio ioe aee ooo]

  # letters < 11 chars and no numbers
  # HITS = %w[aaa aaaa abaa azaz monkey longstring stringlong]
  # MISSES = %w[aa aa1 aa0 b9b 6zz longstringz m_m ff5 666 anotherlongstring]

  MAX_SUCCESSES = HITS.size + MISSES.size

  # Setup the various Regular Expression operators, etc..
  RELEMENTS = %w[. ? * + ( ) \[ \] - | ^ $ \\ : @ / { }]
  %w[A b B d D S s W w z Z].each do |chr|
    RELEMENTS << "\\#{chr}"
  end
  %w[alnum alpha blank cntrl digit lower print punct space upper xdigit].each do |special|
    RELEMENTS << "[:#{special}:]"
  end
  ('a'..'z').each do |chr|
    RELEMENTS << chr
  end
  ('A'..'Z').each do |chr|
    RELEMENTS << chr
  end
  (0..9).each do |chr|
    RELEMENTS << chr.to_s
  end

  START_SIZE = 8

  attr_accessor :operators, :successes

  def initialize(ary = [])
    @operators = ary
    if ary.length < 1
      START_SIZE.times do
        @operators << random_op
      end
    end
    @score = 0
    @decay = 1
    make_regexp
  end

  def make_regexp
    begin
      @regexp = Regexp.new( @operators.join("") )
    rescue
      # "INVALID Regexp"
      @regexp = nil
      @score = -1000
    end
  end

  def random_op
    RELEMENTS[rand(RELEMENTS.size)]
  end

  def decay
    @decay -= 1
  end

  def test
    @successes = 0
    if @regexp
      HITS.each do |hit|
        result = (hit =~ @regexp)
        if result != nil
          reward
        end
      end
      MISSES.each do |miss|
        result = (miss =~ @regexp)
        if result == nil
          reward
        end
      end
    end
    @score = @successes
    self
  end

  def reward
    @successes += 1
  end

  def cross other
    len = size
    olen = other.size
    split = rand(len)
    ops = []
    @operators.length.times do |num|
      if num < split
        ops << @operators[num]
      else
        ops << other.operators[num + (olen - len)]
      end
    end
    Attempt.new ops
  end

  # apply a random mutation, you don't have to use all of them
  def mutate
    send [:flip, :add_rand, :add_first, :add_last, :sub_rand, :sub_first, :sub_last, :swap][rand(8)]
    make_regexp
    self
  end

  ## mutate methods
  def flip
    @operators[rand(size)] = random_op
  end
  def add_rand
    @operators.insert rand(size), random_op
  end
  def add_first
    @operators.insert 0, random_op
  end
  def add_last
    @operators << random_op
  end
  def sub_rand
    @operators.delete_at rand(size)
  end
  def sub_first
    @operators.delete_at 0
  end
  def sub_last
    @operators.delete_at size
  end
  def swap
    to = rand(size)
    begin
      from = rand(size)
    end while to == from
    @operators[to], @operators[from] = @operators[from], @operators[to]
  end

  def regexp_to_s
    @operators.join("")
  end

  def <=> other
    score <=> other.score
  end

  def size
    @operators.length
  end

  def to_s
    "#{regexp_to_s} #{score}"
  end

  def dup
    Attempt.new @operators.dup
  end

  def score
    if @score > 0
      ret = case
      when (size > START_SIZE * 2)
        @score-20
      when size > START_SIZE
        @score-2
      else
        @score #+ START_SIZE - size
      end
      ret + @decay
    else
      @score + @decay
    end
  end

  def == other
    to_s == other.to_s
  end

  def stats
    puts "Regexp #{@regexp.inspect}"
    puts "Length #{@operators.length}"
    puts "Successes #{@successes}/#{MAX_SUCCESSES}"
    puts "HITS"
    HITS.each do |hit|
      result = (hit =~ @regexp)
      if result == nil
        puts "\tFAIL #{hit}"
      else
        puts "\tOK #{hit} #{result}"
      end
    end
    puts "MISSES"
    MISSES.each do |miss|
      result = (miss =~ @regexp)
      if result == nil
          puts "\tOK #{miss}"
        else
          puts "\tFAIL #{miss} #{result}"
      end
    end
  end

end

$stderr.reopen("/dev/null", "w") # turn off stderr to stop streams of bad rexexp messages

# find some seed attempt values
results = []
10000.times do
  a = Attempt.new
  a.test
  if a.score > 0
    # puts "#{a.regexp_to_s} #{a.score}"
    results << a
  end
end

results.sort!.reverse!

puts "SEED ATTEMPTS"
puts results[0..9]

old_result = nil

LOOP_COUNT.times do |i|
  results = results[0..9]
  results.map {|r| r.decay }
  3.times do
    new_results = results.map {|r| r.dup.mutate.test}
    results.concat new_results
    new_results = results.map {|r| r.cross( results[rand(10)] ).test }
    results.concat new_results
  end
  new_results = []
  20.times do
    new_results << Attempt.new.test
  end
  results.concat new_results
  results.sort!.reverse!
  if old_result != results[0].score
    old_result = results[0].score
  end
  puts "#{i}   #{results[0]}"
end
puts "\n--------------------------------------------------"
puts "Winner! #{results[0]}"
puts "--------------------------------------------------\n"
results[0].stats

Lessons learned from playing with this code.

从这段代码中学到的经验教训。

Overall, it appears that running shorter loops several times is most likely to produce a usable result. However, this may be due to my implementation rather than the nature of genetic algorithms.

总的来说，似乎多次运行较短的循环最有可能产生可用的结果。然而，这可能是由于我的实施而不是遗传算法的本质。

You may get results that work but still contain parts that are gibberish.

您可能会得到有效的结果但仍包含乱码的部分。

You are going to need a pretty firm grasp of regular expressions to understand how many of the results actually achieve what they do.

您将需要非常牢固地掌握正则表达式，以了解有多少结果实际上实现了它们的功能。

Ultimately your time is probably much better spent learning Regular Expressions than trying to use this code as a shortcut. I realise that the questioner may not have had that motive and the reason I tried this was because it was an interesting idea.

最终，花在学习正则表达式上的时间要好于尝试将此代码用作快捷方式。我意识到提问者可能没有这种动机，我尝试这个的原因是因为这是一个有趣的想法。

There are many trade-offs in the results. The more diverse HITS and MISSES you supply, the longer it will take to produce a result and the more loops you will have to run. Having less of each will likely produce a result that is either massively specific to your supplied strings or so generic that it wouldn't be useful in a real world situation.

结果中有许多权衡取舍。您提供的HITS和MISSES越多样化，产生结果所需的时间越长，您必须运行的循环越多。每个较少的结果可能会产生一个结果，该结果要么大量特定于您提供的字符串，要么是通用的，以至于它在现实世界中不会有用。

I have also hard-coded some assumptions, such as marking down expressions which get too long.

我还对一些假设进行了硬编码，例如标记过长的表达式。

#3

import just released a free tool to derive regex patterns from sets of example strings: "give it examples of data you want to pull out, and it will programmatically generate and test a regular expression."

import刚刚发布了一个免费工具，可以从示例字符串集中派生出正则表达式模式：“给出它想要提取的数据示例，它将以编程方式生成并测试正则表达式。”

https://regexpgen.import.io/

https://regexpgen.import.io/

Its free but do need a login to use it.

它是免费的，但需要登录才能使用它。

Disclaimer: I work at import.io (that's how i know this exists)

免责声明：我在import.io工作（这就是我知道这存在的方式）

#4

This site actually lets you generate a regex from the sample text. You pick the part of a text string that you want the regular expression for and it generates it for you in the language of your choice.

该站点实际上允许您从示例文本生成正则表达式。您选择要使用正则表达式的文本字符串的一部分，然后使用您选择的语言为您生成该字符串。

Take a look at it, it has an example explained in its FAQ - https://txt2re.com/index.php3?d=faq

看看它，它的常见问题解答中有一个例子 - https://txt2re.com/index.php3?d=faq