From: Robert Klemme <bob.news@...>
Date: 2004-08-14T00:21:07+09:00
Subject: Re: Implementation ideas?  Flexible string matching

------=_NextPart_000_0035_01C48159.99848D90
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit


"Kirk Haines" <khaines@enigo.com> schrieb im Newsbeitrag
news:20040813142908.M67018@enigo.com...
> On Fri, 13 Aug 2004 17:36:11 +0900, Robert Klemme wrote
>
> > Yep.
> >
> > > I've written something similar for
> > > Regexp::English but the optimization itself is quite slow and takes
up
> > > lots of resources. (Because it needs to build the trie.)
> >
> > Well, it was ok in my case because the word list didn't change and I
> > put the generated regexp into code.  Although I'm not sure that it
> > was really that slow.  Lemmesee...  IMHO Theoretically it should be
> > around O(n*m) with n the number of words and m the average word
length.
>
> I would love to see your script, Robert.  I was flirting in my head with
the
> thought that if one took all of the regexes and broken them into shared
> pieces and made a tree out of them, one could walk down the tree of
pieces
> until one found the complete regex that made the match.  Neat to see my
> brain wasn't totally off base with the idea.  So I want to take the
regexp
> your script builds and benchmark it against the current state of affairs
> with simple hash based fixed string matching as well as the basic match
the
> fixed strings then iterate through the regexes approach and see how
overall
> performance shakes out.

Ha,

found it!  Nothing gets lost on a good sorted and well sized hard disk.
:-))
(see attachment, one is the script and it needs the tree implementation in
the other file)

Have fun!

Kind regards

    robert

------=_NextPart_000_0035_01C48159.99848D90
Content-Type: application/octet-stream;
	name="create-rx.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filename="create-rx.rb"

#!/usr/bin/ruby

require 'tree'

class CharTreeNode < Tree::TreeNode
  attr_accessor :char

  def initialize(ch=nil, parent=nil)
    super(parent)
    @char = ch
  end

  def get_char_child(ch)
    each do |child|
      return child if ch == child.char
    end

    self.class.new(ch, self)
  end

  def <=> (node)
    self.char <=> node.char
  end

  def create_rx(io)
    io << char.chr if char

    case children.size
    when 0
      # nothing to do
    when 1
      children[0].create_rx(io)
    else
      # create a non capturing group
      io << "(?:"

      join = nil

      children.sort.each do |child|
        if join
          io << join
        else
          join = "|"
        end

        child.create_rx(io)
      end

      io << ")"
    end

    io
  end
end

class CharTree < Tree
  def initialize
    super CharTreeNode.new
  end

  def create_rx
    str = StringIO.new
    root.create_rx str
    str.string
  end
end



tree = CharTree.new

while ( line = gets )
  line.chomp!
  line.strip!

  node = tree.root

  line.each_byte do |ch|
    node = node.get_char_child ch
  end
end

puts tree.create_rx


------=_NextPart_000_0035_01C48159.99848D90
Content-Type: application/octet-stream;
	name="Tree.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filename="Tree.rb"


require 'stringio'

class Tree
  attr_accessor :root

  def initialize(root=nil)
    @root = root
  end

  def dump(io = StringIO.new)
    @root.dump(io, 0) if @root
    io
  end

  def dfs(&b)
    self.root.dfs &b if self.root
    self
  end

  def bfs(&b)
    self.root.bfs &b if self.root
    self
  end


  class TreeNode
    include Enumerable

    attr_accessor :parent
    attr_reader :children

    def initialize(parent=nil)
      self.parent = parent
      @children = []
    end

    def parent=(parent)
      if @parent
        @parent.children.delete self
      end

      @parent = parent

      if @parent
        @parent.children.push self unless @parent.children.include? self
      end
    end

    def path
      parents = []

      n = self

      while n
        parents.unshift n
        n = n.parent
      end

      parents
    end

    def each
      @children.each {|ch| yield ch}
    end

    def empty?
      @children.empty?
    end

    def flatten
      # result=[].concat self.children
      result=[self]
      dfs {|n| result.push n}
      result
    end

    def count_leafs
      count = 0

      dfs do |n|
        count += 1 if n.leaf?
      end

      count
    end

    def leaf?
      self.children.empty?
    end

    def last_node?
      self.children.each do |ch|
        return false if ch.kind_of? TreeNode
      end

      return true
    end

    def root?
      self.parent.nil?
    end

    def child_of?(node)
      n = self

      while n
        return true if node == n
        n = n.parent
      end

      false
    end

    def level
      level = 0
      p = self.parent

      while p
        level += 1
        p = p.parent
      end

      level
    end

    def dfs
      stack = [self]

      until stack.empty?
        n = stack.pop

        yield n
        stack.concat n.children if n.respond_to? :children
      end

      self
    end

    def bfs
      queue = [self]

      until stack.empty?
        n = stack.shift

        yield n
        stack.concat n.children if n.respond_to? :children
      end

      self
    end

    def dump(io, level=0)
      io << ("  " * level) << self.to_s << "\n"

      level += 1

      self.children.each do |ch|
        if ch.kind_of? TreeNode
          ch.dump(io, level)
        else
          io << ("  " * level) << ch.to_s << "\n"
        end
      end
    end

  end # class TreeNode

end

------=_NextPart_000_0035_01C48159.99848D90--