http://wiki.karljones.com/index.php?action=history&feed=atom&title=Ukkonen%27s_algorithm 2026-10-23T21:11:14Z Revision history for this page on the wiki MediaWiki 1.24.2 http://wiki.karljones.com/index.php?title=Ukkonen%27s_algorithm&diff=15486&oldid=prev 2016-05-17T01:54:08Z

<p></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 01:54, 17 May 2016</td> </tr><tr><td colspan="2" class="diff-lineno">Line 9:</td> <td colspan="2" class="diff-lineno">Line 9:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>This order addition of characters gives Ukkonen's algorithm its &quot;on-line&quot; property.</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>This order addition of characters gives Ukkonen's algorithm its &quot;on-line&quot; property.</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>The original algorithm presented by Peter Weiner proceeded backward from the last character to the first one from the shortest to the longest suffix.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>The original algorithm presented by <ins class="diffchange diffchange-inline">[[</ins>Peter Weiner<ins class="diffchange diffchange-inline">]] </ins>proceeded backward from the last character to the first one from the shortest to the longest suffix.</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>A simpler algorithm was found by [[Edward M. McCreight]], going from the longest to the shortest suffix.</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>A simpler algorithm was found by [[Edward M. McCreight]], going from the longest to the shortest suffix.</div></td></tr> </table>

Karl Jones http://wiki.karljones.com/index.php?title=Ukkonen%27s_algorithm&diff=15482&oldid=prev 2016-05-17T01:36:37Z

<p>Created page with &quot;In <a href="/index.php/Computer_science" title="Computer science">computer science</a>, &#039;&#039;&#039;Ukkonen&#039;s algorithm&#039;&#039;&#039; is a linear-time, <a href="/index.php/Online_algorithm" title="Online algorithm">online algorithm</a> for constructing <a href="/index.php?title=Suffix_tree&amp;action=edit&amp;redlink=1" class="new" title="Suffix tree (page does not exist)">suffix trees</a>, proposed by <a href="/index.php?title=Esko_Ukkonen&amp;action=edit&amp;redlink=1" class="new" title="Esko Ukkonen (page does not exist)">Esko Ukkonen</a> in 1995....&quot;</p> <p><b>New page</b></p><div>In [[computer science]], '''Ukkonen's algorithm''' is a linear-time, [[online algorithm]] for constructing [[Suffix tree|suffix trees]], proposed by [[Esko Ukkonen]] in 1995.<br /> <br /> == Description ==<br /> <br /> The algorithm begins with an implicit suffix tree containing the first character of the string.<br /> <br /> Then it steps through the string adding successive characters until the tree is complete.<br /> <br /> This order addition of characters gives Ukkonen's algorithm its &quot;on-line&quot; property.<br /> <br /> The original algorithm presented by Peter Weiner proceeded backward from the last character to the first one from the shortest to the longest suffix.<br /> <br /> A simpler algorithm was found by [[Edward M. McCreight]], going from the longest to the shortest suffix.<br /> <br /> == See also ==<br /> <br /> * [[Algorithm]]<br /> * [[Online algorithm]]<br /> <br /> == External links ==<br /> <br /> * [https://en.wikipedia.org/wiki/Online_algorithm Ukkonen's algorithm] @ Wikipedia<br /> <br /> <br /> [[Category:Algorithms]]<br /> [[Category:Computer science]]</div>

Karl Jones