luikore/triez

require 'triez'

# create triez with (default value type) int64, and setting default value 0
t = Triez.new

# The default value is 0
t['foo'] #=> 0

# available options for value_type:
# - :int64  -- signed 64 bit integer
# - :object -- ruby object, but note that:
#              if the object is beyond simple types like NilClass, TrueClass, Integer,
#              it will take additional heap space
t = Triez.new value_type: :int64

# more flexible with object type [*see note below]
t = Triez.new value_type: :object

# get the value type
t.value_type

# set a different default value
t = Triez.new value_type: :object, default: 'hello'

# insert or change value
t['key'] = 100

# insert a key with default value
t << 'key'

# batch change values under all suffices/prefices/substrings of a key
t.change_all(:suffix, 'key') {|old_value| ...calculate new value }
t.change_all(:prefix, 'key') {|old_value| ...calculate new value }
# enumerates all occurences of substrings of the key
t.change_all(:substring, 'key') {|old_value| ...calculate new value }

# size of inserted keys
t.size

# search with exact match
t.has_key? 'key'
t['key']

# prefixed search (iterate over values under a prefix), available options are:
# - limit: max items, `nil` means no limit
# - sort: whether iterate in alphabetic order, default is true
t.search_with_prefix(prefix, limit: 10, sort: true) do |suffix, value|
  ...
end

# if no block given, an array in the form of [[suffix, value]] is returned
t.search_with_prefix('prefix')

# enumerate all keys and values in the order of binary collation
t.each do |key, value|
  ...
end

# iterate stored keys which are prefices of a given string, from shallow to deep
t.walk string do |k, v|
  ...
end

t = Triez.new value_type: :object
t['Tom'] = {name: 'Tom', sex: 'Female'}
t['Tree'] = [:leaf, :trunk, :root]

require 'triez'
words = %w[readme, rot, red, rah, rasterization]
t = Triez.new
words.each do |word|
  t[word] = 1
end
t.search_with_prefix 're' do |suffix|
  puts "candidate: re#{suffix}"
end

require 'triez'
sequences = {
  'ACTGAAAAAAACTG' => 1,
  'ATACGGTCCA' => 2,
  'GCTTGTACGT' => 3
}
t = Triez.new

# build suffix tree
sequences.each do |seq, id|
  t.change_all(:suffix, seq){id}
end

t.search_with_prefix 'CGGT' do |_, id|
  puts id #=> 2
end

# coding: utf-8
require 'triez'
sentences = %w[
  万塘路一锅鸡
  去文二路一锅鸡吃饭
  来一锅鸡顶盒
  一锅鸡胗
]

# value is bitset representing id of the sentence
# in ruby we can use integers of arbitrary length as bitsets
t = Triez.new value_type: :object, default: 0

sentences.each_with_index do |sentence, i|
  elem = 1 << i
  t.change_all :substring, sentence do |v|
    # union
    v | elem
  end
end

# longest common substring
lcs = ''

# find the key tagged with universe
universe = (1 << sentences.size) - 1
t.each do |k, v|
  lcs = k if k.size > lcs.size and v == universe
end

puts lcs #=> 一锅鸡

ruby 1.9.3p374 (2013-01-15 revision 38858) [x86_64-darwin12.2.1]
2.3 GHz Intel Core i7