Class: AhoCorasick::KeywordTree

Inherits:

Object

• Object
• AhoCorasick::KeywordTree

Defined in:

ext/ruby-ahocorasick.c

Class Method Summary

• .from_file ⇒ Object

  Creates a new KeywordTree and loads the dictionary from a file.

Instance Method Summary

• #add_string ⇒ Object (also: #<<)

  Adds a sequence to this KeywordTree.

• #find_all ⇒ Object (also: #search)

  Search the current tree.

• #initialize ⇒ Object constructor

  Creates a new KeywordTree.

• #make ⇒ Object

  It freezes the current KeywordTree.

• #size ⇒ Object

  Returns the size of this KeywordTree.

Constructor Details

#initialize ⇒ Object

Creates a new KeywordTree

require 'ahocorasick'
kwt = Ahocorasick::KeywordTree.new

# File 'ext/ruby-ahocorasick.c', line 58

static VALUE 
rb_kwt_init(VALUE self)
{ 
  AC_STRUCT * tree;
  struct kwt_struct_data *kwt_data;

  kwt_data = ALLOC(struct kwt_struct_data);
  tree     = ac_alloc();
  DATA_PTR(self) = kwt_data;
  kwt_data->tree            = tree;
  kwt_data->last_id         = 1;
  kwt_data->dictionary_size = 0;
  kwt_data->is_frozen       = 0;
  return self;
}

Class Method Details

.from_file ⇒ Object

Creates a new KeywordTree and loads the dictionary from a file

% cat dict0.txt
foo
bar
base

k= AhoCorasick::KeywordTree.from_file "dict0.txt"
k.search("basement").size # => 1

# File 'ext/ruby-ahocorasick.c', line 266

static VALUE
rb_kwt_new_from_file(int argc, VALUE *argv, VALUE klass)
{ 

  // TODO: 
  //  * use rb_kwt_add_string
  //  * use rb_io* to handle the file

  struct kwt_struct_data *kwt_data;
  char word[1024];
  int id;
  VALUE self;
  VALUE f_string;
  FILE *dictionary;

  rb_scan_args(argc, argv, "10", &f_string);
 
  id = 0;
  SafeStringValue( f_string );
  self= rb_class_new_instance( 0, NULL, klass );
  KeywordTree( self, kwt_data );

  dictionary = fopen( RSTRING( f_string )->ptr, "r" );
  if(dictionary == NULL)
    rb_raise(rb_eRuntimeError, "Cannot open `%s\". No such file?", RSTRING(f_string)->ptr);

  while(fgets(word, 1024, dictionary) != NULL) {
    ac_add_string(kwt_data->tree, word, strlen(word)-1, id++);
    kwt_data->dictionary_size++;
  }

  kwt_data->last_id= id+1;
  fclose(dictionary);
  return self;
}

Instance Method Details

#add_string ⇒ Object Also known as: <<

Adds a sequence to this KeywordTree.

kwt.add_string("foo1$21^ 98N3 ba>Z")
kwt << "bar" # using the alias

Note: you can also specify the id, a number between 1 and k

kwt.add_string "bar", 123 # => 123

This id should be unique in the context of the current tree.

Returns the id of the inserted object.

kwt.add_string("test", 18) # => 18
kwt.add_string("baz") # => 19

# File 'ext/ruby-ahocorasick.c', line 217

static VALUE
rb_kwt_add_string(int argc, VALUE *argv, VALUE self)
{ 
  VALUE v_string, v_id;
  struct kwt_struct_data *kwt_data;
  char * string;
  int id;

  rb_scan_args(argc, argv, "11", &v_string, &v_id);
 
  Check_Type(v_string, T_STRING);
  string= RSTRING(v_string)->ptr;
  KeywordTree(self, kwt_data);

  if(kwt_data->is_frozen == 1)
    rb_raise(rb_eRuntimeError, "Cannot add `%s\" into a frozen tree.", string);

  if(v_id == Qnil) {
    id = kwt_data->last_id;
  } else if(TYPE(v_id) != T_FIXNUM) {
    rb_raise(rb_eRuntimeError, "Please use a number from 1 to K as id, or leave nil to auto-generate one. `%s\" given.", RSTRING(v_id)->ptr);
  } else if(NUM2INT(v_id) <= 0) {
    rb_raise(rb_eRuntimeError, "Please use a number from 1 to K as id, or leave nil to auto-generate one. `%d\" given.", NUM2INT(v_id));
  } else {
    id= NUM2INT(v_id);
  }
  
  if(ac_add_string(kwt_data->tree, string, strlen(string), id) == 0)
    rb_raise(rb_eRuntimeError, "Failed to add `%s\", duplicate id `%d\"?", string, id);

  kwt_data->last_id= id + 1;
  kwt_data->dictionary_size++;
  return INT2FIX(id);
}

#find_all ⇒ Object Also known as: search

Search the current tree.

It returns an array on hashes, e.g.

[ { :id => int, :value => int, :starts_at => int, :ends_at => int}, { ... } ]

Returns an empty array when the search didn’t return any result.

# assuming a valid KeywordTree kwt object:
kwt.add_string("one")
kwt.add_string("two")

kwt.search( "moved two times already" ).each  do | result |
  result[:id] # => 2
  result[:ends_at] # => 9
  result[:starts_at] # => 6
  result[:value] # => two
end # => 1

# File 'ext/ruby-ahocorasick.c', line 131

static VALUE
rb_kwt_find_all(int argc, VALUE *argv, VALUE self)
{
  char * remain;        // returned by ac_search, the remaing text to search
  int lgt, id, ends_at, starts_at; // filled in by ac_search: the length of the result, the id, and starts_at/ends_at position
  VALUE v_result;  // one result, as hash
  VALUE v_results; // all the results, an array

  VALUE v_search;  // search string, function argument
  struct kwt_struct_data *kwt_data;
  
  // one mandatory argument.
  rb_scan_args(argc, argv, "1", &v_search);
  // it should be string.
  Check_Type(v_search, T_STRING);
  // get the structure
  KeywordTree(self, kwt_data);
  // freeze the tree, if not already
  if(kwt_data->is_frozen == 0) {
    if(ac_prep( kwt_data->tree ) == 0) 
      rb_raise(rb_eRuntimeError, "Cannot freeze the tree");
    kwt_data->is_frozen = 1;
  }
  // prepare the return value
  v_results= rb_ary_new();
  // fail quickly and return the empty array
  if(kwt_data->dictionary_size == 0) 
    return v_results;
  // prepare the search
  ac_search_init(kwt_data->tree, RSTRING( v_search )->ptr, RSTRING( v_search )->len);
  // loop trought the results
  while((remain= ac_search(kwt_data->tree, &lgt, &id, &ends_at)) != NULL) {
    // this is an individual result as a hash
    v_result= rb_hash_new();
    rb_hash_aset( v_result, sym_id,        INT2FIX(id) );
    rb_hash_aset( v_result, sym_starts_at, INT2FIX( ends_at - lgt - 1 ) );
    rb_hash_aset( v_result, sym_ends_at,   INT2FIX( ends_at - 1 ) );
    rb_hash_aset( v_result, sym_value, rb_str_new(remain, lgt) );
    rb_ary_push( v_results, v_result );
  }
  // reopen the tree
  kwt_data->is_frozen= 0;
  return v_results;
}

#make ⇒ Object

It freezes the current KeywordTree.

Note: This method is called internally by search

require 'ahocorasick'

kwt = Ahocorasick::KeywordTree.new

kwt.add_string("one")
kwt.add_string("two")
kwt.make()

# File 'ext/ruby-ahocorasick.c', line 90

static VALUE 
rb_kwt_make(VALUE self)
{ 
  struct kwt_struct_data *kwt_data;
  KeywordTree(self, kwt_data);

  if(kwt_data->is_frozen == 1)
    return Qtrue;
  
  if(ac_prep( kwt_data->tree ) == 1) {
    kwt_data->is_frozen = 1;
    return Qtrue;
  }

  rb_raise(rb_eRuntimeError, "Cannot freeze the tree");
}

#size ⇒ Object

Returns the size of this KeywordTree

kwt.add_string("foo")
kwt.add_string("bar")
kwt.size #=> 2

# File 'ext/ruby-ahocorasick.c', line 187

static VALUE 
rb_kwt_size(VALUE self)
{ 
  struct kwt_struct_data *kwt_data;
  KeywordTree(self, kwt_data);

  return INT2FIX(kwt_data->dictionary_size);
}