No release in over 3 years
Low commit activity in last 3 years
This gem provides ruby library with Aho-Corasick substring search algorithm implementation.
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
 Dependencies

Development

~> 1.17
~> 0.1
~> 0.12
~> 10.0
~> 3.0
~> 0.67.0
~> 0.16.0
 Project Readme

Trie Substring Search

Build Status

Maintainability codecov

Installation

Implementation of text syntax analyzer, which represents text as non symetric trie of chars or substrings by dictionary or list of keywords. Similar to Aho-Corasick algorithm, but with modifications, there is removed suffixes and added recovering text from the trie.

Add this line to your application's Gemfile:

gem 'trie-substring-search'

And then execute:

$ bundle

Or install it yourself as:

$ gem install trie-substring-search

Usage

    # Array of words in the dictionary
dictionary = %w[he she her his him he they their she]
    # Initialize trie
    # types of trie to build :full, :flat(WIP) and :aho_corasick(WIP)
tss = TSS::Trie.new(dictionary, :full)
    # Parse text and receive array of all occurrences of words in texts with indexes of word in dictionary
tss.parse('he their them height have then their shelter')
    # => [{:word=>"he", :indexes=>[0, 5]},
    #  {:word=>"their", :indexes=>[7]},
    #  {:word=>"he", :indexes=>[0, 5]},
    #  {:word=>"he", :indexes=>[0, ''$'\200\274\240\235\357''U'5]},
    #  {:word=>"he", :indexes=>[0, 5]},
    #  {:word=>"he", :indexes=>[0, 5]},
    #  {:word=>"their", :indexes=>[7]},
    #  {:word=>"he", :indexes=>[0, 5]},
    #  {:word=>"she", :indexes=>[1, 8]},
    #  {:word=>"he", :indexes=>[0, 5]}]
    # Add additional words to the dictionary
tss.extend_dictionary(%w[our it them])
    # Get end vertex of word 'they'
vertex = tss.root.get_child('s').get_child('h').get_child('e')
    # => #<ACT::Vertex:0x000055cabb2399d0
    #  @char="e",
    #  @children=[],
    #  @end_indexes=[1, 8],
    #  @parent=
    #   #<ACT::Vertex:0x000055cabb239ac0
    #    @char="h",
    #    @children=[#<ACT::Vertex:0x000055cabb2399d0 ...>],
    #    @end_indexes=[],
    #    @parent=
    #     #<ACT::Vertex:0x000055cabb239bb0
    #      @char="s",
    #      @children=[#<ACT::Vertex:0x000055cabb239ac0 ...>],
    # get array of indexes of word
vertex.end_indexes
    # => [1, 8]
    # Recover word from trie with indexes in dictionary
tss.backtrace_to_word(vertex)
    # => {:word=>"she", :indexes=>[1, 8]}

Index of word in dictionary can be used to get relations with additional array with external data(or collection, or can be easily replaced by foreign key in the future). If dictionary contain duplicates, then you will get few indexes in result.

Benchmark

dictionary:                            100000 words
number of executions with uniq text:   44555
results of benchmark:

user       system     total       real
1.749733   0.116561   1.866294 (  1.876876)

Development

Contributing

TBD Improvements:

- TODO: Mode providing ability to return whole words, that contain substring from dictionary
- TODO: Suffix references is not implemented. Just now it contains full syntax tree, so it is less memory efficient then original Aho-Corasick algorithm.
- TODO: Maybe, will be good to implement next features for trie build stage:
  -  post optimization of vertex connections, creating suffixes
  -  some parallelism
  -  pre optimization of a dictionary.