Lập trình lấy được biểu thức chính quy từ một chuỗi

Question

Tôi muốn nhập một chuỗi và trả về một cụm từ thông dụng có thể được sử dụng để mô tả cấu trúc của chuỗi. Regex sẽ được sử dụng để tìm thêm các chuỗi có cấu trúc giống như đầu tiên.

Đây là mục đích mơ hồ vì tôi chắc chắn sẽ bỏ lỡ một trường hợp ai đó trong cộng đồng SO sẽ bắt.

Vui lòng đăng bất kỳ và tất cả các cách có thể để thực hiện việc này.

Answer 1

Câu trả lời nhỏ nhặt, và có lẽ không phải là những gì bạn muốn, là: trả về chuỗi đầu vào (với ký tự đặc biệt regex được thoát). Đó luôn là cụm từ thông dụng khớp với chuỗi.

Nếu bạn muốn xác định cấu trúc nhất định, bạn phải cung cấp thêm thông tin về loại cấu trúc bạn muốn xác định. Không có thông tin đó, vấn đề được nêu một cách mơ hồ và có nhiều giải pháp khả thi. Ví dụ, chuỗi đầu vào 'aba' có thể được mô tả như

'aba'

'aba *'

'aba?'

'ab \ w'

'\ w {3}'

'(.) B \ 1'

, vv

Answer 2

Xin lỗi vì chiều dài của này. Tôi lấy tiền đề của điều này như một thách thức nhỏ và đã đưa ra với một bằng chứng về khái niệm trong Ruby.

Tôi đã nghiên cứu giả định rằng bạn có thể cung cấp một số chuỗi phải khớp với cụm từ thông dụng (HITS) và một số không khớp (MISSES).

Tôi dựa trên mã về triển khai ngây thơ của thuật toán di truyền. Xem các ghi chú ở dưới cùng cho những suy nghĩ của tôi về sự thành công, hoặc cách khác, của phương pháp này.

LOOP_COUNT = 100 

class Attempt 

    # let's try email 
    HITS = %w[j@j.com j@j.co.uk gates@microsoft.com sales@microsoft.com sjobs@apple.com sales@apple.com frddy@aol.com thing1@charity.org sales@mybad.org.uk thing.one@drseuss.com] 
    MISSES = %w[j@j j@j@.com j.com @domain.com nochance eric@google. eric@google.com. 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 

Bài học rút ra từ việc chơi với mã này.

Nhìn chung, có vẻ như chạy vòng ngắn hơn nhiều lần có nhiều khả năng tạo ra kết quả khả dụng nhất. Tuy nhiên, điều này có thể là do việc thực hiện của tôi thay vì bản chất của các thuật toán di truyền.

Bạn có thể nhận được kết quả hoạt động nhưng vẫn chứa các phần sai ngữ pháp.

Bạn sẽ cần nắm vững các biểu thức chính quy để hiểu có bao nhiêu kết quả thực sự đạt được những gì họ làm.

Cuối cùng, thời gian của bạn có thể chi tiêu tốt hơn cho việc học Biểu thức chính quy hơn là cố gắng sử dụng mã này làm lối tắt. Tôi nhận ra rằng người hỏi có thể không có động cơ đó và lý do tôi thử điều này là bởi vì đó là một ý tưởng thú vị.

Có nhiều sự đánh đổi trong kết quả. HITS và MISSES đa dạng hơn bạn cung cấp, càng mất nhiều thời gian để tạo ra kết quả và nhiều vòng lặp hơn bạn sẽ phải chạy.Có ít của mỗi có khả năng sẽ tạo ra một kết quả đó là một trong hai ồ ạt cụ thể cho chuỗi cung cấp của bạn hoặc như vậy chung chung rằng nó sẽ không hữu ích trong một tình huống thế giới thực.

Tôi cũng đã mã hóa một số giả định, chẳng hạn như đánh dấu các biểu thức quá dài.

Answer 3

nhập chỉ phát hành công cụ miễn phí để lấy mẫu regex từ tập hợp chuỗi ví dụ: "cung cấp ví dụ về dữ liệu bạn muốn kéo ra và tạo lập trình và kiểm tra biểu thức chính quy theo chương trình".

https://regexpgen.import.io/

miễn phí nhưng cần đăng nhập để sử dụng.

Disclaimer: Tôi làm việc tại import.io (đó là làm thế nào tôi biết điều này tồn tại)

Answer 4

site Điều này thực sự cho phép bạn tạo một regex từ các văn bản mẫu. Bạn chọn một phần của chuỗi văn bản mà bạn muốn biểu thức chính quy và nó tạo ra nó cho bạn bằng ngôn ngữ bạn chọn.

Hãy nhìn vào nó, nó có một ví dụ giải thích trong FAQ của nó - https://txt2re.com/index.php3?d=faq