Skip to content

Instantly share code, notes, and snippets.

@fl00r
Created October 28, 2016 11:17
Show Gist options
  • Save fl00r/86fc392fccb0e9e99075728fffb106bb to your computer and use it in GitHub Desktop.
Save fl00r/86fc392fccb0e9e99075728fffb106bb to your computer and use it in GitHub Desktop.
Trie
properties = box.schema.space.create('properties')
properties:create_index('primary', {parts = {1, 'str'}, type = 'HASH', unique = true, if_not_exists = true})
properties:replace({'node_id', 0})
nodes = box.schema.space.create('nodes')
nodes:create_index('primary', {parts = {1, 'num', 2, 'str'}, type = 'TREE', unique = true, if_not_exists = true})
function load_words()
local words = "/opt/dict/words"
for line in io.lines(words) do
insert_string(line:lower())
end
end
function insert_node(node, char, word)
box.begin()
id = box.space.properties:update('node_id', {{'+', 2, 1}})
t = box.space.nodes:insert({node, char, id[2], word})
box.commit()
return t
end
function insert_string(str)
local node = 0
local len = #str
for i = 1, len do
local c = str:sub(i, i)
local data = (box.space.nodes:select({node, c})[1] or insert_node(node, c, i == len))
node = data[3]
end
end
function find(prefix, max)
local node = 0
local data = nil
local res = {}
for i = 1, #prefix do
local c = prefix:sub(i, i)
data = box.space.nodes:select({node, c})[1]
if data == nil then break; end
node = data[3]
end
if data == nil then
return res
else
local queue = {{prefix, data[3]}}
if data[4] then res[#res+1] = prefix; end
if #res < max then
local i = 1
repeat
local node = queue[i]
local all_nodes = box.space.nodes:select(node[2])
for j = 1, #all_nodes do
local n = all_nodes[j]
local p = node[1] .. n[2]
queue[#queue + 1] = {p, n[3]}
if n[4] then res[#res+1] = p; end
if #res >= max then break; end
end
if #res >= max then break; end
i = i + 1
until(queue[i] == nil)
end
return res
end
end
-- tarantool:3301> find("anato", 100)
-- ---
-- - - anatox
-- - anatole
-- - anatoly
-- - anatomy
-- - anatolic
-- - anatomic
-- - anatoxin
-- - anatocism
-- - anatolian
-- - anatomism
-- - anatomist
-- - anatomize
-- - anatopism
-- - anatomical
-- - anatomizer
-- - anatomically
-- - anatomization
-- - anatomicomedical
-- - anatomicosurgical
-- - anatomopathologic
-- - anatomicobiological
-- - anatomicopathologic
-- - anatomopathological
-- - anatomicochirurgical
-- - anatomicophysiologic
-- - anatomicopathological
-- - anatomicophysiological
--
-- tarantool:3301> find("app", 10)
-- ---
-- - - appay
-- - appet
-- - apple
-- - apply
-- - appall
-- - appeal
-- - appear
-- - append
-- - appete
-- - appius
--
-- tarantool:3301> find("robo", 10)
-- ---
-- - - robot
-- - robomb
-- - robotry
-- - roborant
-- - roborate
-- - roborean
-- - robotian
-- - robotism
-- - robotize
-- - roboreous
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment