<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="en-GB">
	<id>https://wiki.gideros.rocks/index.php?action=history&amp;feed=atom&amp;title=Dictionary_tree_search</id>
	<title>Dictionary tree search - Revision history</title>
	<link rel="self" type="application/atom+xml" href="https://wiki.gideros.rocks/index.php?action=history&amp;feed=atom&amp;title=Dictionary_tree_search"/>
	<link rel="alternate" type="text/html" href="https://wiki.gideros.rocks/index.php?title=Dictionary_tree_search&amp;action=history"/>
	<updated>2026-11-17T20:53:40Z</updated>
	<subtitle>Revision history for this page on the wiki</subtitle>
	<generator>MediaWiki 1.43.11</generator>
	<entry>
		<id>https://wiki.gideros.rocks/index.php?title=Dictionary_tree_search&amp;diff=23253&amp;oldid=prev</id>
		<title>MoKaLux: Created page with &quot;__TOC__  &#039;&#039;&#039;https://forum.gideros.rocks/discussion/821/compressed-ternary-dags-for-dictionary-search&#039;&#039;&#039;  === Compressed ternary DAGs for dictionary search === &#039;&#039;&#039;atilim&#039;&#039;&#039;, on...&quot;</title>
		<link rel="alternate" type="text/html" href="https://wiki.gideros.rocks/index.php?title=Dictionary_tree_search&amp;diff=23253&amp;oldid=prev"/>
		<updated>2023-12-08T00:02:23Z</updated>

		<summary type="html">&lt;p&gt;Created page with &amp;quot;__TOC__  &amp;#039;&amp;#039;&amp;#039;https://forum.gideros.rocks/discussion/821/compressed-ternary-dags-for-dictionary-search&amp;#039;&amp;#039;&amp;#039;  === Compressed ternary DAGs for dictionary search === &amp;#039;&amp;#039;&amp;#039;atilim&amp;#039;&amp;#039;&amp;#039;, on...&amp;quot;&lt;/p&gt;
&lt;p&gt;&lt;b&gt;New page&lt;/b&gt;&lt;/p&gt;&lt;div&gt;__TOC__&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;https://forum.gideros.rocks/discussion/821/compressed-ternary-dags-for-dictionary-search&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
&lt;br /&gt;
=== Compressed ternary DAGs for dictionary search ===&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;atilim&amp;#039;&amp;#039;&amp;#039;, one of Gideros founder, implemented an optimized version of the Ternary Search Trees algorithm for Gideros!&lt;br /&gt;
&lt;br /&gt;
*It&amp;#039;s fast (Samsung SII, the search speed is about 30000-50000 searches per second)&lt;br /&gt;
*It&amp;#039;s compact and GC friendly&lt;br /&gt;
*After compression the dictionary file is usually smaller than the original file&lt;br /&gt;
&lt;br /&gt;
=== Creating Dictionaries ===&lt;br /&gt;
You can create your dictionaries by using the code &amp;#039;&amp;#039;&amp;#039;buildtst.cpp&amp;#039;&amp;#039;&amp;#039; or use &amp;#039;&amp;#039;&amp;#039;buildtst.exe&amp;#039;&amp;#039;&amp;#039; with the &amp;#039;&amp;#039;&amp;#039;cmd&amp;#039;&amp;#039;&amp;#039; line. You can download the zip file:&lt;br /&gt;
&lt;br /&gt;
==== &amp;#039;&amp;#039;&amp;#039;[[Media:Dictionary_tree_search_cpp.zip]]&amp;#039;&amp;#039;&amp;#039; ====&lt;br /&gt;
&lt;br /&gt;
Steps to convert a &amp;#039;&amp;#039;&amp;#039;.txt&amp;#039;&amp;#039;&amp;#039; file to a compressed &amp;#039;&amp;#039;&amp;#039;.dic&amp;#039;&amp;#039;&amp;#039; file suitable for fast search:&lt;br /&gt;
* go in the folder where &amp;quot;&amp;#039;&amp;#039;buildtst.exe&amp;#039;&amp;#039;&amp;quot; is&lt;br /&gt;
* put your .txt file in that same folder&lt;br /&gt;
* in windows explorer navbar type &amp;#039;&amp;#039;cmd&amp;#039;&amp;#039;&lt;br /&gt;
* then in the &amp;#039;&amp;#039;&amp;#039;cmd editor&amp;#039;&amp;#039;&amp;#039; enter:&lt;br /&gt;
&amp;lt;syntaxhighlight lang=&amp;quot;c&amp;quot;&amp;gt;&lt;br /&gt;
buildtst.exe yourfile.txt yourfile.dic&lt;br /&gt;
&amp;lt;/syntaxhighlight&amp;gt;&lt;br /&gt;
&lt;br /&gt;
That&amp;#039;s it, your text file has been converted to a dic file.&lt;br /&gt;
&lt;br /&gt;
=== Gideros Search Algorithm ===&lt;br /&gt;
&amp;lt;syntaxhighlight lang=&amp;quot;lua&amp;quot;&amp;gt;&lt;br /&gt;
-- bg&lt;br /&gt;
application:setBackgroundColor(0xaa5500)&lt;br /&gt;
&lt;br /&gt;
local f = io.open(&amp;quot;sowpods.dic&amp;quot;, &amp;quot;rb&amp;quot;)&lt;br /&gt;
local dic = f:read(&amp;quot;*all&amp;quot;)&lt;br /&gt;
f:close()&lt;br /&gt;
&lt;br /&gt;
local function search(dic, str)&lt;br /&gt;
	local pos = 1&lt;br /&gt;
	local node = 1&lt;br /&gt;
&lt;br /&gt;
	while node ~= 0 do&lt;br /&gt;
		local char = str:byte(pos) or 0&lt;br /&gt;
		local index = (node - 1) * 10&lt;br /&gt;
		local splitchar = dic:byte(index + 1)&lt;br /&gt;
		&lt;br /&gt;
		if char &amp;lt; splitchar then&lt;br /&gt;
			local b1, b2, b3 = dic:byte(index + 2, index + 4)&lt;br /&gt;
			node = b1 + b2 * 256 + b3 * 65536&lt;br /&gt;
		elseif char == splitchar then&lt;br /&gt;
			if char == 0 then&lt;br /&gt;
				return true&lt;br /&gt;
			end&lt;br /&gt;
			pos = pos + 1&lt;br /&gt;
			local b1, b2, b3 = dic:byte(index + 5, index + 7)&lt;br /&gt;
			node = b1 + b2 * 256 + b3 * 65536&lt;br /&gt;
		else&lt;br /&gt;
			local b1, b2, b3 = dic:byte(index + 8, index + 10)&lt;br /&gt;
			node = b1 + b2 * 256 + b3 * 65536&lt;br /&gt;
		end&lt;br /&gt;
	end&lt;br /&gt;
	return false&lt;br /&gt;
end&lt;br /&gt;
&lt;br /&gt;
print(search(dic, &amp;quot;ZYMOSIMETER&amp;quot;))	--&amp;gt; should be true&lt;br /&gt;
print(search(dic, &amp;quot;GIDEROS&amp;quot;))		--&amp;gt; should be false&lt;br /&gt;
print(search(dic, &amp;quot;LANGUAGE&amp;quot;))		--&amp;gt; should be true&lt;br /&gt;
print(search(dic, &amp;quot;SYSTEM&amp;quot;))		--&amp;gt; should be true&lt;br /&gt;
&amp;lt;/syntaxhighlight&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&lt;br /&gt;
=== The Full Project ===&lt;br /&gt;
==== &amp;#039;&amp;#039;&amp;#039;[[Media:Dictionary_tree_search_algo.zip]]&amp;#039;&amp;#039;&amp;#039; ====&lt;br /&gt;
&lt;br /&gt;
&lt;br /&gt;
{{GIDEROS IMPORTANT LINKS}}&lt;/div&gt;</summary>
		<author><name>MoKaLux</name></author>
	</entry>
</feed>