tag:blogger.com,1999:blog-83552993493250448572024-03-05T11:48:48.749-08:00Jaringan InformasiAnthon R. Tampubolonhttp://www.blogger.com/profile/04493652019575515292noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-8355299349325044857.post-56440274867817816812011-10-23T09:21:00.000-07:002011-10-23T09:22:46.711-07:00Knuth-Morris-Pratt algorithm<a accesskey="1" href="http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm#section0" name="section0"></a> <br />
<div class="body"><table border="0"><tbody>
<tr><td><h1>String matching</h1><h2>Knuth-Morris-Pratt algorithm</h2></td><td align="right" valign="top"> <a href="http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmp.htm" target="_top"><img alt="German version" border="0" height="19" src="http://www.inf.fh-flensburg.de/lang/symbols/de.gif" title="German version" width="19" /></a> <a accesskey="6" href="http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/indexen.htm" target="_top"><img alt="up" border="0" height="19" src="http://www.inf.fh-flensburg.de/lang/symbols/up.gif" title="up" width="19" /></a> </td></tr>
</tbody></table><h3 class="header"><a href="http://www.blogger.com/post-edit.g?blogID=8355299349325044857&postID=5644027486781781681" name="section1">Idea</a></h3>After a shift of the pattern, the naive algorithm has forgotten all information about previously matched symbols. So it is possible that it re-compares a text symbol with different pattern symbols again and again. This leads to its worst case complexity of Θ(<var>nm</var>) (<var>n</var>: length of the text, <var>m</var>: length of the pattern). <br />
The algorithm of Knuth, Morris and Pratt <a href="http://www.blogger.com/post-edit.g?blogID=8355299349325044857&postID=5644027486781781681" title="D.E. Knuth, J.H. Morris, V.R. Pratt: Fast Pattern Matching in Strings. SIAM Journal of Computing 6, 2, 323-350 (1977)">[KMP 77]</a> makes use of the information gained by previous symbol comparisons. It never re-compares a text symbol that has matched a pattern symbol. As a result, the complexity of the searching phase of the Knuth-Morris-Pratt algorithm is in <var>O</var>(<var>n</var>). <br />
However, a preprocessing of the pattern is necessary in order to analyze its structure. The preprocessing phase has a complexity of <var>O</var>(<var>m</var>). Since <var>m</var><img alt="<=" src="http://www.inf.fh-flensburg.de/lang/symbols/le.gif" /><var>n</var>, the overall complexity of the Knuth-Morris-Pratt algorithm is in <var>O</var>(<var>n</var>). <br />
<div class="abst"><br />
<a name='more'></a><br />
</div><h3 class="header"><a href="http://www.blogger.com/post-edit.g?blogID=8355299349325044857&postID=5644027486781781681" name="section2">Basic definitions</a></h3><div class="box"><div class="line1"><span class="def">Definition:</span> Let <var>A</var> be an alphabet and <var>x</var> = <var>x</var><sub>0</sub> ... <var>x</var><sub><var>k</var>-1,</sub> <var>k</var> <img alt="element" src="http://www.inf.fh-flensburg.de/lang/symbols/elem.gif" /> <img alt="natural numbers" src="http://www.inf.fh-flensburg.de/lang/symbols/n.gif" /> a string of length <var>k</var> over <var>A</var>. </div>A <span class="di">prefix</span> of <var>x</var> is a substring <var>u</var> with <br />
<div class="ind"><var>u</var> = <var>x</var><sub>0</sub> ... <var>x</var><sub><var>b</var>-1</sub> where <var>b</var> <img alt="element" src="http://www.inf.fh-flensburg.de/lang/symbols/elem.gif" /> {0, ..., <var>k</var>} </div>i.e. <var>x</var> starts with <var>u</var>. <br />
A <span class="di">suffix</span> of <var>x</var> is a substring <var>u</var> with <br />
<div class="ind"><var>u</var> = <var>x</var><sub><var>k</var>-<var>b</var></sub> ... <var>x</var><sub><var>k</var>-1</sub> where <var>b</var> <img alt="element" src="http://www.inf.fh-flensburg.de/lang/symbols/elem.gif" /> {0, ..., <var>k</var>} </div>i.e. <var>x</var> ends with <var>u</var>. <br />
A prefix <var>u</var> of <var>x</var> or a suffix <var>u</var> of <var>x</var> is called a <span class="di">proper</span> prefix or suffix, respectively, if <var>u</var><img alt="not equal" src="http://www.inf.fh-flensburg.de/lang/symbols/ne.gif" /><var>x</var>, i.e. if its length <var>b</var> is less than <var>k</var>. <br />
A <span class="di">border</span> of <var>x</var> is a substring <var>r</var> with <br />
<div class="ind"><var>r</var> = <var>x</var><sub>0</sub> ... <var>x</var><sub><var>b</var>-1</sub> and <var>r</var> = <var>x</var><sub><var>k</var>-<var>b</var></sub> ... <var>x</var><sub><var>k</var>-1</sub> where <var>b</var> <img alt="element" src="http://www.inf.fh-flensburg.de/lang/symbols/elem.gif" /> {0, ..., <var>k</var>-1} </div>A border of <var>x</var> is a substring that is both proper prefix and proper suffix of <var>x</var>. We call its length <var>b</var> the <span class="di">width</span> of the border. </div><div class="box"><div class="line1"><span class="def">Example:</span> Let <var>x</var> = abacab. The proper prefixes of <var>x</var> are </div><div class="ind">ε, a, ab, aba, abac, abaca </div>The proper suffixes of <var>x</var> are <br />
<div class="ind">ε, b, ab, cab, acab, bacab </div>The borders of <var>x</var> are <br />
<div class="ind">ε, ab </div>The border ε has width 0, the border ab has width 2. </div>The empty string ε is always a border of <var>x</var>, for all <var>x</var> <img alt="element" src="http://www.inf.fh-flensburg.de/lang/symbols/elem.gif" /> <var>A</var><sup><small>+</small></sup>. The empty string ε itself has no border. <br />
The following example illustrates how the shift distance in the Knuth-Morris-Pratt algorithm is determined using the notion of the border of a string. <br />
<div class="box"><div class="line1"><span class="def">Example:</span> </div><table border="0" cellpadding="0" cellspacing="0" class="pattern"><tbody>
<tr><th width="16">0</th><th width="16">1</th><th width="16">2</th><th width="16">3</th><th width="16">4</th><th width="16">5</th><th width="16">6</th><th width="16">7</th><th width="16">8</th><th width="16">9</th><th width="16">...</th></tr>
<tr><td>a</td><td>b</td><td>c</td><td>a</td><td>b</td><td>c</td><td>a</td><td>b</td><td>d </td><td><br />
</td><td><br />
</td></tr>
<tr><td><span style="color: green;">a</span></td><td><span style="color: green;">b</span></td><td><span style="color: green;">c</span></td><td><span style="color: green;">a</span></td><td><span style="color: green;">b</span></td><td><span style="color: red;">d</span></td><td><br />
</td><td><br />
</td><td><br />
</td><td><br />
</td><td><br />
</td></tr>
<tr><td><br />
</td><td><br />
</td><td><br />
</td><td>a</td><td>b</td><td>c</td><td>a</td><td>b</td><td>d</td><td><br />
</td><td><br />
</td></tr>
</tbody></table>The symbols at positions 0, ..., 4 have matched. Comparison c-d at position 5 yields a mismatch. The pattern can be shifted by 3 positions, and comparisons are resumed at position 5. <br />
The shift distance is determined by the widest border of the matching prefix of <var>p</var>. In this example, the matching prefix is abcab, its length is <var>j</var> = 5. Its widest border is ab of width <var>b</var> = 2. The shift distance is <var>j</var> – <var>b</var> = 5 – 2 = 3. </div>In the preprocessing phase, the width of the widest border of each prefix of the pattern is determined. Then in the search phase, the shift distance can be computed according to the prefix that has matched.<br />
<div class="abst"><br />
</div><h3 class="header"><a href="http://www.blogger.com/post-edit.g?blogID=8355299349325044857&postID=5644027486781781681" name="section3">Preprocessing</a></h3><div class="box"><div class="line1"><span class="def">Theorem:</span> Let <var>r</var>, <var>s</var> be borders of a string <var>x</var>, where |<var>r</var>| < |<var>s</var>|. Then <var>r</var> is a border of <var>s</var>. </div></div><div class="box"><div class="line1"><span class="def">Proof:</span> Figure 1 shows a string <var>x</var> with borders <var>r</var> and <var>s</var>. Since <var>r</var> is a prefix of <var>x</var>, it is also a proper prefix of <var>s</var>, because it is shorter than <var>s</var>. But <var>r</var> is also a suffix of <var>x</var> and, therefore, proper suffix of <var>s</var>. Thus <var>r</var> is a border of <var>s</var>. </div></div><div class="ind"><table border="0"><tbody>
<tr><td height="10"><br />
</td></tr>
<tr><td align="center"><table border="0"><tbody>
<tr> <td align="center" valign="bottom"><img alt="Borders r, s of a string x" src="http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/rand.gif" /></td> </tr>
</tbody></table></td></tr>
<tr><td align="center"></td></tr>
<tr><td height="10"><br />
</td></tr>
<tr><td align="center"><small>Figure 1: <i>Borders r</i>, <i>s of a string x</i></small></td></tr>
<tr><td height="10"><br />
</td></tr>
</tbody></table></div>If <var>s</var> is the widest border of <var>x</var>, the next-widest border <var>r</var> of <var>x</var> is obtained as the widest border of <var>s</var> etc. <br />
<div class="abst"><br />
</div><div class="box"><div class="line1"><span class="def">Definition:</span> Let <var>x</var> be a string and <var>a</var> <img alt="element" src="http://www.inf.fh-flensburg.de/lang/symbols/elem.gif" /> <var>A</var> a symbol. A border <var>r</var> of <var>x</var> can be <span class="di">extended by <var>a</var></span>, if <var>ra</var> is a border of <var>xa</var>. </div></div><div class="ind"><table border="0"><tbody>
<tr><td height="10"><br />
</td></tr>
<tr><td align="center"><table border="0"><tbody>
<tr> <td align="center" valign="bottom"><img alt="Extension of a border" src="http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/rand2.gif" /></td> </tr>
</tbody></table></td></tr>
<tr><td align="center"></td></tr>
<tr><td height="10"><br />
</td></tr>
<tr><td align="center"><small>Figure 2: <i>Extension of a border</i></small></td></tr>
<tr><td height="10"><br />
</td></tr>
</tbody></table></div>Figure 2 shows that a border <var>r</var> of width <var>j</var> of <var>x</var> can be extended by <var>a</var>, if <var>x</var><sub><var>j</var></sub> = <var>a</var>. <br />
<div class="abst"><br />
</div>In the preprocessing phase an array <var>b</var> of length <var>m</var><small>+</small>1 is computed. Each entry <var>b</var>[<var>i</var>] contains the width of the widest border of the prefix of length <var>i</var> of the pattern (<var>i</var> = 0, ..., <var>m</var>). Since the prefix ε of length <var>i</var> = 0 has no border, we set <var>b</var>[0] = -1. <br />
<div class="ind"><table border="0"><tbody>
<tr><td height="10"><br />
</td></tr>
<tr><td align="center"><table border="0"><tbody>
<tr> <td align="center" valign="bottom"><img alt="Prefix of length i of the pattern with border of width b[i]" src="http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/rand4.gif" /></td> </tr>
</tbody></table></td></tr>
<tr><td align="center"></td></tr>
<tr><td height="10"><br />
</td></tr>
<tr><td align="center"><small>Figure 3: <i>Prefix of length i of the pattern with border of width b</i>[<i>i</i>]</small></td></tr>
<tr><td height="10"><br />
</td></tr>
</tbody></table></div>Provided that the values <var>b</var>[0], ..., <var>b</var>[<var>i</var>] are already known, the value of <var>b</var>[<var>i</var><small>+</small>1] is computed by checking if a border of the prefix <var>p</var><sub>0</sub> ... <var>p</var><sub><var>i</var>-1</sub> can be extended by symbol <var>p</var><sub><var>i</var></sub>. This is the case if <var>p</var><sub><var>b</var>[<var>i</var>]</sub> = <var>p</var><sub><var>i</var></sub> (Figure 3). The borders to be examined are obtained in decreasing order from the values <var>b</var>[<var>i</var>], <var>b</var>[<var>b</var>[<var>i</var>]] etc. <br />
The preprocessing algorithm comprises a loop with a variable <var>j</var> assuming these values. A border of width <var>j</var> can be extended by <var>p</var><sub><var>i</var></sub>, if <var>p</var><sub><var>j</var></sub> = <var>p</var><sub><var>i</var></sub>. If not, the next-widest border is examined by setting <var>j</var> = <var>b</var>[<var>j</var>]. The loop terminates at the latest if no border can be extended (<var>j</var> = -1). <br />
After increasing <var>j</var> by the statement <tt>j++</tt> in each case <var>j</var> is the width of the widest border of <var>p</var><sub>0</sub> ... <var>p</var><sub><var>i</var></sub>. This value is written to <var>b</var>[<var>i</var><small>+</small>1] (to <var>b</var>[<var>i</var>] after increasing <var>i</var> by the statement <tt>i++</tt>). <br />
<div class="abst"><br />
</div><h5><span class="sbh">Preprocessing algorithm</span></h5><table border="0" cellpadding="0" cellspacing="0"><tbody>
<tr><td class="code"><pre class="java"><span class="codekeyword">void</span> kmpPreprocess()
{
<span class="codekeyword">int</span> i=0, j=-1;
b[i]=j;
<span class="codekeyword">while</span> (i<m)
{
<span class="codekeyword">while</span> (j>=0 && p[i]!=p[j]) j=b[j];
i++; j++;
b[i]=j;
}
}
</pre></td></tr>
</tbody></table><div class="box"><div class="line1"><span class="def">Example:</span> For pattern <var>p</var> = ababaa the widths of the borders in array <var>b</var> have the following values. For instance we have <var>b</var>[5] = 3, since the prefix ababa of length 5 has a border of width 3. </div><div class="ind"><table border="0" cellpadding="0" cellspacing="0" class="pattern"><tbody>
<tr><th class="headcol"><var>j</var>:</th><td width="16">0</td><td width="16">1</td><td width="16">2</td><td width="16">3</td><td width="16">4</td><td width="16">5</td><td width="16">6</td></tr>
<tr><th class="headcol"><var>p</var>[<var>j</var>]:</th><td>a</td><td>b</td><td>a</td><td>b</td><td>a</td><td>a</td><td><br />
</td></tr>
<tr><th class="headcol"><var>b</var>[<var>j</var>]:</th><td>-1</td><td>0</td><td>0</td><td>1</td><td>2</td><td>3</td><td>1</td></tr>
</tbody></table></div></div><div class="abst"><br />
</div><h3 class="header"><a href="http://www.blogger.com/post-edit.g?blogID=8355299349325044857&postID=5644027486781781681" name="section4">Searching algorithm</a></h3>Conceptually, the above preprocessing algorithm could be applied to the string <var>pt</var> instead of <var>p</var>. If borders up to a width of <var>m</var> are computed only, then a border of width <var>m</var> of some prefix <var>x</var> of <var>pt</var> corresponds to a match of the pattern in <var>t</var> (provided that the border is not self-overlapping) (Figure 4). <br />
<div class="ind"><table border="0"><tbody>
<tr><td height="10"><br />
</td></tr>
<tr><td align="center"><table border="0"><tbody>
<tr> <td align="center" valign="bottom"><img alt="Border of length m of a prefix x of pt" src="http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/rand3.gif" /></td> </tr>
</tbody></table></td></tr>
<tr><td align="center"></td></tr>
<tr><td height="10"><br />
</td></tr>
<tr><td align="center"><small>Figure 4: <i>Border of length m of a prefix x of pt</i></small></td></tr>
<tr><td height="10"><br />
</td></tr>
</tbody></table></div>This explains the similarity between the preprocessing algorithm and the following searching algorithm. <br />
<div class="abst"><br />
</div><h5><span class="sbh">Searching algorithm</span></h5><table border="0" cellpadding="0" cellspacing="0"><tbody>
<tr><td class="code"><pre class="java"><span class="codekeyword">void</span> kmpSearch()
{
<span class="codekeyword">int</span> i=0, j=0;
<span class="codekeyword">while</span> (i<n)
{
<span class="codekeyword">while</span> (j>=0 && t[i]!=p[j]) j=b[j];
i++; j++;
<span class="codekeyword">if</span> (j==m)
{
report(i-j);
j=b[j];
}
}
}
</pre></td></tr>
</tbody></table>When in the inner while loop a mismatch at position <var>j</var> occurs, the widest border of the matching prefix of length <var>j</var> of the pattern is considered (Figure 5). Resuming comparisons at position <var>b</var>[<var>j</var>], the width of the border, yields a shift of the pattern such that the border matches. If again a mismatch occurs, the next-widest border is considered, and so on, until there is no border left (<var>j</var> = -1) or the next symbol matches. Then we have a new matching prefix of the pattern and continue with the outer while loop. <br />
<div class="ind"><table border="0"><tbody>
<tr><td height="10"><br />
</td></tr>
<tr><td align="center"><table border="0"><tbody>
<tr> <td align="center" valign="bottom"><img alt="Shift of the pattern when a mismatch at position j occurs" src="http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/rand5.gif" /></td> </tr>
</tbody></table></td></tr>
<tr><td align="center"></td></tr>
<tr><td height="10"><br />
</td></tr>
<tr><td align="center"><small>Figure 5: <i>Shift of the pattern when a mismatch at position j occurs</i></small></td></tr>
<tr><td height="10"><br />
</td></tr>
</tbody></table></div>If all <var>m</var> symbols of the pattern have matched the corresponding text window (<var>j</var> = <var>m</var>), a function <i>report</i> is called for reporting the match at position <var>i</var>-<var>j</var>. Afterwards, the pattern is shifted as far as its widest border allows. <br />
In the following example the comparisons performed by the searching algorithm are shown, where matches are drawn in green and mismatches in red. <br />
<div class="box"><div class="line1"><span class="def">Example:</span> </div><table border="0" cellpadding="0" cellspacing="0" class="pattern"><tbody>
<tr><th width="16">0</th><th width="16">1</th><th width="16">2</th><th width="16">3</th><th width="16">4</th><th width="16">5</th><th width="16">6</th><th width="16">7</th><th width="16">8</th><th width="16">9</th><th width="16">...</th><th width="16"><br />
</th><th width="16"><br />
</th></tr>
<tr><td>a</td><td>b</td><td>a</td><td>b</td><td>b</td><td>a</td><td>b</td><td>a</td><td>a </td><td><br />
</td><td><br />
</td><td><br />
</td><td><br />
</td></tr>
<tr><td><span style="color: green;">a</span></td><td><span style="color: green;">b</span></td><td><span style="color: green;">a</span></td><td><span style="color: green;">b</span></td><td><span style="color: red;">a</span></td><td>c</td><td><br />
</td><td><br />
</td><td><br />
</td><td><br />
</td><td><br />
</td><td><br />
</td><td><br />
</td></tr>
<tr><td><br />
</td><td><br />
</td><td>a</td><td>b</td><td><span style="color: red;">a</span></td><td>b</td><td>a</td><td>c</td><td><br />
</td><td><br />
</td><td><br />
</td><td><br />
</td><td><br />
</td></tr>
<tr><td><br />
</td><td><br />
</td><td><br />
</td><td><br />
</td><td><span style="color: red;">a</span></td><td>b</td><td>a</td><td>b</td><td>a</td><td>c</td><td><br />
</td><td><br />
</td><td><br />
</td></tr>
<tr><td><br />
</td><td><br />
</td><td><br />
</td><td><br />
</td><td><br />
</td><td><span style="color: green;">a</span></td><td><span style="color: green;">b</span></td><td><span style="color: green;">a</span></td><td><span style="color: red;">b</span></td><td>a</td><td>c</td><td><br />
</td><td><br />
</td></tr>
<tr><td><br />
</td><td><br />
</td><td><br />
</td><td><br />
</td><td><br />
</td><td><br />
</td><td><br />
</td><td>a</td><td><span style="color: red;">b</span></td><td>a</td><td>b</td><td>a</td><td>c</td></tr>
</tbody></table></div><div class="abst"><br />
</div><h3 class="header"><a href="http://www.blogger.com/post-edit.g?blogID=8355299349325044857&postID=5644027486781781681" name="section5">Analysis</a></h3>The inner while loop of the preprocessing algorithm decreases the value of <var>j</var> by at least 1, since <var>b</var>[<var>j</var>] < <var>j</var>. The loop terminates at the latest when <var>j</var> = -1, therefore it can decrease the value of <var>j</var> at most as often as it has been increased previously by <tt>j++</tt>. Since <tt>j++</tt> is executed in the outer loop exactly <var>m</var> times, the overall number of executions of the inner while loop is limited to <var>m</var>. The preprocessing algorithm therefore requires <var>O</var>(<var>m</var>) steps. <br />
From similar arguments it follows that the searching algorithm requires <var>O</var>(<var>n</var>) steps. The above example illustrates this: the comparisons (green and red symbols) form "stairs". The whole staircase is at most as wide as it is high, therefore at most 2<var>n</var> comparisons are performed. <br />
Since <var>m</var><img alt="<=" src="http://www.inf.fh-flensburg.de/lang/symbols/le.gif" /><var>n</var> the overall complexity of the Knuth-Morris-Pratt algorithm is in <var>O</var>(<var>n</var>). <br />
<div class="abst"><br />
</div>Sumber :</div><div class="body"><a href="http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm">http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm </a></div>Anthon R. Tampubolonhttp://www.blogger.com/profile/04493652019575515292noreply@blogger.com0tag:blogger.com,1999:blog-8355299349325044857.post-79637123711370890992011-09-25T10:03:00.000-07:002011-10-23T09:11:34.643-07:00Personal Brand<div class="MsoNormal" style="margin-bottom: .0001pt; margin-bottom: 0cm;"><br />
</div><div class="MsoNormal">Blog ini digunakan sebagai media komunikasi dan monitoring perkembangan penulisan paper ilmiah dengan judul <b>Penyaringan Konten Dengan Menggunakan String Matching Pada Proses Deep Packet Inspection</b> sebagai tugas akhir matakuliah Jaringan Informasi. Artikel-artikel dalam blog ini adalah artikel yang dikumpulkan dari berbagai sumber di internet, buku, tutorial CCNA dan juga tulisan penulis sendiri. Artikel-artikel tersebut digunakan sebagai bahan referensi dalam penyusunan paper ilmiah.</div><div class="MsoNormal" style="margin-bottom: .0001pt; margin-bottom: 0cm;">Paper ilmiah akan dibagi menjadi dua bagian yaitu Konseptual dan Implementasi . Paper konseptual akan membahas : </div><div class="MsoListParagraphCxSpFirst" style="margin-left: 106.35pt; mso-add-space: auto; mso-list: l0 level1 lfo1; text-indent: -18.0pt;">1.<span style="font: 7pt "Times New Roman";"> </span>Definisi Deep Packet Inspection</div><div class="MsoListParagraphCxSpMiddle" style="margin-left: 106.35pt; mso-add-space: auto; mso-list: l0 level1 lfo1; text-indent: -18.0pt;">2.<span style="font: 7pt "Times New Roman";"> </span>Network Packet</div><div class="MsoListParagraphCxSpMiddle" style="margin-left: 106.35pt; mso-add-space: auto; mso-list: l0 level1 lfo1; text-indent: -18.0pt;">3.<span style="font: 7pt "Times New Roman";"> </span>Definisi String Matching</div><div class="MsoListParagraphCxSpLast" style="margin-left: 106.35pt; mso-add-space: auto; mso-list: l0 level1 lfo1; text-indent: -18.0pt;">4.<span style="font: 7pt "Times New Roman";"> </span>Algoritma Knuth-Morris-Pratt (KMP)<br />
<a name='more'></a></div><div class="MsoNormal" style="margin-bottom: .0001pt; margin-bottom: 0cm;">Sementara pada Paper implementasi, akan membahas bagaimana implementasi algoritma KMP kedalam proses DPI untuk melakukan penyaringan konten yang masuk kedalam router. langkah-langkah pengujiannya adalah sebagai berikut :<br />
<span style="font-size: small;"> 1. Capturing<br />
Melakukan capture paket data dalam jaringan dengan tools tcpdum menggunakan </span><br />
<span style="font-size: small;"> scenario yang ada dan diharapkan menghasilkan sebuah data capture</span><br />
<span style="font-size: small;"></span><br />
2. Extraction</div><div class="MsoListParagraphCxSpFirst" style="margin-left: 2.0cm; mso-add-space: auto; mso-list: l1 level1 lfo2; tab-stops: 3.0cm; text-indent: -18.0pt;"> Melakukan Extract ke sebuah file untuk di analisis menggunakan metode Match String</div><div class="MsoNormal"> 3. Analalizyng<br />
Melakukan analisis menggunakan algoritma KMP terhadap paket data yang telah<br />
capture sebelumnya dan diharapkan menghasilkan 2 jenis data yaitu Match dan<br />
unMatch <br />
4. Action<br />
Mengambil tindakan terhadap hasil yang diberikan oleh algoritma KMP yaitu<br />
memberikan persetujuan kepada paket yang berjenis Match dan melakukan<br />
pemblokiran terhadap paket yang berjenis unMatch.<br />
<br />
Pada paper kedua ini, penulis menggunakan metodologi pengujian langsung di 3 buah komputer, dimana satu komputer akan bertindak sebagai router.<br />
<br />
Demikian Personal Brand ini dibuat sebagai pendahuluan dalam penulisan paper ilmiah ini.</div><div class="MsoNormal"><br />
</div><div class="MsoNormal">Data Penulis :</div><div class="MsoNormal" style="margin-bottom: .0001pt; margin-bottom: 0cm;">Nama : Anthon Roberto Tampubolon</div><div class="MsoNormal" style="margin-bottom: .0001pt; margin-bottom: 0cm;">Nim : 23510311</div><div class="MsoNormal"><br />
</div>Anthon R. Tampubolonhttp://www.blogger.com/profile/04493652019575515292noreply@blogger.com0tag:blogger.com,1999:blog-8355299349325044857.post-7992087883174332122011-09-21T08:36:00.000-07:002011-10-23T09:11:46.066-07:00Contoh Penerapan String Matching - Algoritma Bruter Force<div class="separator" style="clear: both; text-align: center;"><br />
</div><iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.blogger.com/video.g?token=AD6v5dyXz_0konpXzLqiQvH0Pb43cBYq9jORN2QVR8Bzgr_JLk_p9rS_dFQm7FaIna95uwxRkWeUUrkEV-duCkcPDQ' class='b-hbp-video b-uploaded' frameborder='0'></iframe><br />
<br />
<a name='more'></a><br />
<br />
Sumber : http://www.youtube.com/watch?v=46cTe4MAKRw&feature=relatedAnthon R. Tampubolonhttp://www.blogger.com/profile/04493652019575515292noreply@blogger.com0tag:blogger.com,1999:blog-8355299349325044857.post-42073594352625798892011-09-21T08:19:00.000-07:002011-10-23T09:11:54.928-07:00Definisi Deep Packet InspectionDeep Packet Inspection <br />
<br />
DPI adalah sebuah teknologi yang diterapkan di Router atau peralatan pemantau lainnya, yang memungkinkan untuk memantau aliran data secara real-time dan membuat keputusan terhadap aliran data tersebut.<br />
DPI dapat melakukan pemeriksaan terhadap data dari header information hingga payload yang merupakan isi dari data-data yang dikirim melalui Router.<br />
<span style="font-size: 12pt; line-height: 150%;"> </span> <br />
<div class="MsoNormal" style="line-height: 150%; margin-bottom: .0001pt; margin-bottom: 0cm; text-align: justify;"><span style="font-size: 12pt; line-height: 150%;">Beberapa fungsi dari DPI diantaranya:</span></div><div class="MsoListParagraphCxSpFirst" style="line-height: 150%; mso-list: l0 level1 lfo1; text-align: justify; text-indent: -18.0pt;"><span style="font-size: 12pt; line-height: 150%;">1.<span style="font: 7pt "Times New Roman";"> </span></span><i><span style="font-size: 12pt; line-height: 150%;">Network security</span></i><span style="font-size: 12pt; line-height: 150%;"></span></div><div class="MsoListParagraphCxSpMiddle" style="line-height: 150%; margin-bottom: .0001pt; margin-bottom: 0cm; mso-add-space: auto; text-align: justify;"><span style="font-size: 12pt; line-height: 150%;">Sebagian besar DPI, digunakan oleh operator jaringan untuk melakukan deteksi serangan dan menyaring lalu lintas malware yang disalurkan kedalam jaringannya.</span><br />
<a name='more'></a></div><div class="MsoListParagraphCxSpMiddle" style="line-height: 150%; margin-top: 12.0pt; mso-add-space: auto; mso-list: l0 level1 lfo1; text-align: justify; text-indent: -18.0pt;"><span style="font-size: 12pt; line-height: 150%;">2.<span style="font: 7pt "Times New Roman";"> </span></span><i><span style="font-size: 12pt; line-height: 150%;">Network management</span></i><span style="font-size: 12pt; line-height: 150%;"></span></div><div class="MsoListParagraphCxSpMiddle" style="line-height: 150%; text-align: justify;"><span style="font-size: 12pt; line-height: 150%;">DPI dapat melakukan pemblokiran terhadap paket-paket yang memenuhi bandwith jaringan, dan juga digunakan untuk meningkatkan optimasi Routing.</span></div><div class="MsoListParagraphCxSpMiddle" style="line-height: 150%; mso-list: l0 level1 lfo1; text-align: justify; text-indent: -18.0pt;"><span style="font-size: 12pt; line-height: 150%;">3.<span style="font: 7pt "Times New Roman";"> </span></span><i><span style="font-size: 12pt; line-height: 150%;">Surveillance</span></i><span style="font-size: 12pt; line-height: 150%;"></span></div><div class="MsoListParagraphCxSpMiddle" style="line-height: 150%; text-align: justify;"><span style="font-size: 12pt; line-height: 150%;">Amerika Serikat memasang peralatan DPI untuk keperluan <i>realtime monitoring</i> yang bekerja sama dengan Badan keamanan nasional. DPI juga digunakan oleh Negara lain untuk memantau internet traffic.</span><span style="font-size: 12pt; line-height: 150%;"></span></div><div class="MsoListParagraphCxSpMiddle" style="line-height: 150%; mso-list: l0 level1 lfo1; text-align: justify; text-indent: -18.0pt;"><span style="font-size: 12pt; line-height: 150%;">4.<span style="font: 7pt "Times New Roman";"> </span></span><i><span style="font-size: 12pt; line-height: 150%;">Content regulation</span></i><span style="font-size: 12pt; line-height: 150%;"></span></div><div class="MsoListParagraphCxSpMiddle" style="line-height: 150%; text-align: justify;"><span style="font-size: 12pt; line-height: 150%;">DPI dapat melakukan pemblokiran terhadap website-website yang dianggap memiliki konten berbahaya ataupun situs porno. Dengan kemampuannya melakukan inspeksi terhadap isi keseluruhan paket-paket yang masuk ke ISP, DPI dapat menerapkan string matching dan melakukan pemblokiran.</span></div><div class="MsoListParagraphCxSpMiddle" style="line-height: 150%; mso-list: l0 level1 lfo1; text-align: justify; text-indent: -18.0pt;"><span style="font-size: 12pt; line-height: 150%;">5.<span style="font: 7pt "Times New Roman";"> </span></span><i><span style="font-size: 12pt; line-height: 150%;">Copyright enforcement</span></i><span style="font-size: 12pt; line-height: 150%;"></span></div><div class="MsoListParagraphCxSpMiddle" style="line-height: 150%; text-align: justify;"><span style="font-size: 12pt; line-height: 150%;">Dengan kemampuan DPI untuk melakukan inspeksi keseluruhan paket, DPI juga dapat digunakan untuk melakukan penyaringan terhadap paket-paket yang memiliki hak cipta seperti Musik, video atau document yang dilindungi oleh hak cipta.</span></div><div class="MsoListParagraphCxSpMiddle" style="line-height: 150%; mso-list: l0 level1 lfo1; text-align: justify; text-indent: -18.0pt;"><span style="font-size: 12pt; line-height: 150%;">6.<span style="font: 7pt "Times New Roman";"> </span></span><i><span style="font-size: 12pt; line-height: 150%;">Ad injection</span></i><span style="font-size: 12pt; line-height: 150%;"></span></div><div class="MsoListParagraphCxSpLast" style="line-height: 150%; text-align: justify;"><span class="longtext"><span style="background: none repeat scroll 0% 0% white; font-size: 12pt; line-height: 150%;">Perusahaan seperti NebuAd dan paket Phorm iklan menawarkan kepada ISP untuk menyuntikkan iklan ke dalam website yang sesuai dengan kepentingan diasumsikan pengguna.</span></span><span style="font-size: 12pt; line-height: 150%;"></span></div><br />
<span style="font-size: 12pt; line-height: 150%;">Sumber :</span><br />
<br />
<div class="MsoListParagraph" style="line-height: 150%; margin-left: 1.0cm; mso-add-space: auto; mso-list: l0 level1 lfo1; text-indent: -1.0cm;"><span style="font-size: 12pt; line-height: 150%;"><span style="font: 7pt "Times New Roman";"></span></span> </div><div class="MsoListParagraph" style="line-height: 150%; margin-left: 0cm; mso-add-space: auto;"><span style="font-size: 12pt; line-height: 150%;">R. Bendrath, "Global technology trends and national regulation: Explaining Variation in the Governance of Deep Packet Inspection" in International Studies Annual Convention New York City, 2009.</span></div><span style="font-size: 12pt; line-height: 150%;"> <a href="http://www.google.co.id/url?sa=t&rct=j&q=global%20technology%20trends%20and%20national%20regulation%3A%20explaining%20variation%20in%20the%20governance%20of%20deep%20packet%20inspection&source=web&cd=1&ved=0CBoQFjAA&url=http%3A%2F%2Fuserpage.fu-berlin.de%2F%7Ebendrath%2FISA09_Paper_Ralf%2520Bendrath_DPI.pdf&ei=1jCkTveYFsWrrAe1_YmOAw&usg=AFQjCNFzXabGBLqTptc1whstnk5t89TQtw&cad=rja">Dowload Paper</a> </span><span style="color: black; font-size: 12pt; line-height: 150%;"></span>Anthon R. Tampubolonhttp://www.blogger.com/profile/04493652019575515292noreply@blogger.com0tag:blogger.com,1999:blog-8355299349325044857.post-43630736610460654732011-09-21T06:44:00.000-07:002011-10-23T09:13:00.488-07:00Perbedaan DPI dan IDS/IPS<div class="MsoNormal" style="line-height: 150%; text-align: justify;"><span class="fullpost"><i style="mso-bidi-font-style: normal;"><span style="font-size: 12pt; line-height: 150%;">Intrusion Detection System (IDS)/ Intrusion Prevention System (IPS)</span></i></span><span class="fullpost"><span style="font-size: 12pt; line-height: 150%;"> menggunakan </span></span><i style="mso-bidi-font-style: normal;"><span style="font-size: 12pt; line-height: 150%;">packet header information</span></i><span style="font-size: 12pt; line-height: 150%;"> sebagai parameter dalam pengambilan keputusan untuk melanjutkan paket atau tidak melanjutkan paket tersebut.</span><span lang="IN" style="font-size: 12pt; line-height: 150%;">.</span><span style="font-size: 12pt; line-height: 150%;"> Keakuratan informasi yang diperoleh menjadi masalah dalam IDS/IPS karena keterbatasannya dalam mendapatkan informasi dari paket yang masuk, dimana IDS/IPS hanya memeriksa 4 layer dalam OSI Layer termasuk didalamnya <i style="mso-bidi-font-style: normal;">IP Packet</i> yang berisi <i style="mso-bidi-font-style: normal;">IP source, IP Destination, Source Port, dan Destination Port</i>. Berbeda dengan IDS/IPS, <i style="mso-bidi-font-style: normal;">Deep Packet Inspection</i> (DPI) dapat melakukan inspeksi pada 7 Layer dalam OSI Layer dimana DPI tidak hanya memeriksa <i style="mso-bidi-font-style: normal;">packet header information</i> saja<i style="mso-bidi-font-style: normal;"> </i>tapi juga memeriksa <i style="mso-bidi-font-style: normal;">payload</i> dalam paket-paket yang masuk dalam jaringan</span><span style="font-size: 12pt; line-height: 150%;"></span><span style="font-size: 12pt; line-height: 150%;"></span><span style="font-size: 12pt; line-height: 150%;">. Sehingga keakuratan informasi yang digunakan sebagai parameter pengambilan keputusan menjadi lebih lengkap, dan dapat membuat system keamanan menjadi lebih kuat. </span><br />
<a name='more'></a></div><div class="MsoNormal" style="line-height: 150%; text-align: justify;"><br />
</div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh3TtJ4LzLNwuhwxb5HZakhV1Vgv1qTQAO6T6TqO0VYhz_0dHeCfrayG13G3q1JHczVUOSUAFcaN8RhlpuUK7QVUyfMBVSX-R6Nx-aQfneBLQRb1VXlHt8GSDq8qKyUqUmiad-9xwqllTf6/s1600/untitled.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="215" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh3TtJ4LzLNwuhwxb5HZakhV1Vgv1qTQAO6T6TqO0VYhz_0dHeCfrayG13G3q1JHczVUOSUAFcaN8RhlpuUK7QVUyfMBVSX-R6Nx-aQfneBLQRb1VXlHt8GSDq8qKyUqUmiad-9xwqllTf6/s320/untitled.JPG" width="320" /></a></div><div class="MsoNormal" style="line-height: 150%; text-align: justify;"><span style="font-size: 12pt; line-height: 150%;"> </span></div><div class="MsoNormal" style="line-height: 150%; text-align: justify;"><span style="font-size: 12pt; line-height: 150%;">Sumber : </span></div><div class="MsoNormal" style="line-height: 150%; text-align: justify;"><span style="font-size: 12pt; line-height: 150%;"> </span></div><div class="MsoNormal" style="line-height: 150%; text-align: justify;"></div><div class="MsoNormal" style="line-height: 150%;"><span style="font-family: TimesNewRoman;">Ajay Chaudhary and Anjali Sardana, “</span><span style="font-size: 12pt; line-height: 150%;">Software Based Implementation Methodologies</span><span style="font-family: TimesNewRoman;"> </span><span style="font-size: 12pt; line-height: 150%;">for Deep Packet Inspection,”</span><span style="font-family: TimesNewRoman;"> in </span><a href="http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5772049"><span style="font-size: 12pt; line-height: 150%;">Information Science and Applications (ICISA)<i style="mso-bidi-font-style: normal;">, </i>2011</span></a><br />
<span style="font-size: 12pt; line-height: 150%;"><a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5772430">Download Paper</a></span></div><div class="MsoNormal" style="line-height: 150%; text-align: justify;"><span style="font-size: 12pt; line-height: 150%;"> </span></div><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"></div>Anthon R. Tampubolonhttp://www.blogger.com/profile/04493652019575515292noreply@blogger.com0tag:blogger.com,1999:blog-8355299349325044857.post-35578686385174452452011-09-21T06:16:00.000-07:002011-10-23T09:53:35.005-07:00String Matching<span style="font-family: "Calibri","sans-serif";">Pencarian string merupakan kegiatan yang sangat sering dilakukan oleh pengguna komputer. Dalam kehidupan sehari-hari, user (pengguna komputer) pasti berhubungan dengan yang namanya pencarian string. Untuk mencari suatu kata misalnya di dalam program Microsoft Word atau pun di web browser seperti Mozilla Firefox atau Internet Explorer, user akan berhubungan dengan bagian find yang merupakan penerapan langsung dari algoritma pencarian string di dalam program aplikasi. Pencarian string di dalam teks disebut juga dengan pencocokan string (string matching atau pattern matching). Perumusan persoalan pencarian string yaitu dengan diberikannya teks atau long string dengan panjang n karakter dan pattern yaitu string yang akan dicari di dalam teks dengan panjang m karakter, dengan m lebih kecil dari n karakter.</span><br />
<a name='more'></a><span style="font-family: "Calibri","sans-serif";"></span><br />
<br />
<span style="font-family: "Calibri","sans-serif";">Ada beberapa algoritma untuk mengimplementasikan metode string matching ini, diantaranya algoritma brute force, algoritma Boyer-Moore, algoritma Knuth-Moris-Pratt(KMP), algoritma Aho-Corasick, dan sebagainya.</span><br />
<br />
<span style="font-family: "Calibri","sans-serif";">Sumber :</span><br />
<br />
<div class="MsoNormal" style="line-height: 150%;"><span style="font-size: 12pt; line-height: 150%;">Dewanto R A., Aradea, “Aplikasi Sms Gateway Dengan Koreksi Kesalahan Menggunakakan Fuzzy String Matching,” in </span><span style="font-size: 12pt; line-height: 150%;">Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007),Yogyakarta,2007</span></div><div class="MsoNormal" style="line-height: 150%;"><span style="font-size: 12pt; line-height: 150%;"><a href="http://journal.uii.ac.id/index.php/Snati/article/view/1642/1417">Download Paper</a></span></div><div class="MsoNormal" style="line-height: 150%;"><br />
</div><span style="font-family: "Calibri","sans-serif";"></span>Anthon R. Tampubolonhttp://www.blogger.com/profile/04493652019575515292noreply@blogger.com0tag:blogger.com,1999:blog-8355299349325044857.post-45041892618732207232011-09-21T06:03:00.000-07:002011-10-23T09:13:19.105-07:00Algoritma Knuth-Morris-Pratt (KMP)<div class="MsoNormal" style="line-height: 150%; margin-bottom: .0001pt; margin-bottom: 0cm; mso-layout-grid-align: none; text-align: justify; text-autospace: none;"><b><span style="font-size: 12pt; line-height: 150%;">Algoritma Knuth-Morris-Pratt (KMP)</span></b></div><div class="MsoNormal" style="line-height: 150%; margin-bottom: .0001pt; margin-bottom: 0cm; mso-layout-grid-align: none; text-align: justify; text-autospace: none;"><span style="font-size: 12pt; line-height: 150%;">Algoritma Knuth Morris Pratt (KMP) dikembangkan oleh D. E. Knuth, bersama dengan J. H. Morris dan V. R. Pratt. Untuk pencarian string dengan algoritma Brute Force , setiap kali ditemukan ketidakcocokan dengan teks, maka pattern akan digeser satu karakter ke kanan. Berbeda dengan algoritma Brute Force, informasi yang digunakan masih dipelihara untuk melakukan jumlah pergeseran. Algoritma menggunakan informasi tersebut untuk membuat pergeseran yang lebih jauh, tidak hanya satu karakter Perbandingan antara algoritma <i style="mso-bidi-font-style: normal;">brute force</i> dengan algoritma KMP ditunjukkan dengan perpindahan posisi pattern terhadap posisi teks. Dimana dalam hal pencocokan string, pattern yang dicocokkan berawal dari kiri teks.</span><br />
<a name='more'></a></div><div class="MsoNormal" style="line-height: 150%; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 0cm; margin-right: 0cm; margin-top: 12.0pt; mso-layout-grid-align: none; text-align: justify; text-autospace: none;"><span style="font-size: 12pt; line-height: 150%;">Kompleksitas algoritma pencocokan string dihitung dari jumlah operasi perbandingan yang dilakukan. Kompleksitas waktu terbaik dari algoritma brute force adalah <i>O</i>(<i>n</i>). Kasus terbaik terjadi jika pada operasi perbandingan, setiap huruf pattern yang dicocokkan dengan awal dari teks adalah sama. Kompleksitas waktu terburuk dari <i style="mso-bidi-font-style: normal;">brute force</i> adalah <i>O</i>(<i>mn</i>).</span></div><div class="MsoNormal" style="line-height: 150%; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 0cm; margin-right: 0cm; margin-top: 12.0pt; mso-layout-grid-align: none; text-align: justify; text-autospace: none;"><span style="font-size: 12pt; line-height: 150%;">Jika dibandingkan dengan algoritma brute force, maka algoritma KMP mempunyai kompleksitas algoritma <i>O</i>(<i>m</i>+<i>n</i>). Definisi yang digunakan, Y adalah suatu alfabet dan </span></div><div class="MsoNormal" style="line-height: 150%; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 72.0pt; margin-right: 0cm; margin-top: 0cm; mso-layout-grid-align: none; text-align: justify; text-autospace: none; text-indent: 36.0pt;"><span style="font-family: "Calibri","sans-serif"; font-size: 11pt; line-height: 115%; position: relative; top: 5.5pt;"> </span> <br />
<div class="MsoNormal" style="line-height: 150%; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 72.0pt; margin-right: 0cm; margin-top: 0cm; mso-layout-grid-align: none; text-align: justify; text-autospace: none; text-indent: 36.0pt;"><span style="font-family: "Calibri","sans-serif"; font-size: 11pt; line-height: 115%; position: relative; top: 5.5pt;"> </span><span style="font-size: 12pt; line-height: 150%;">Z_ = Z_1 Z_1 Z_3… Z_k, k Є N,</span><span style="font-size: 12pt; line-height: 150%;"></span></div><span style="font-size: 12pt; line-height: 150%;"></span></div><div class="MsoNormal" style="line-height: 150%; margin-bottom: .0001pt; margin-bottom: 0cm; mso-layout-grid-align: none; text-align: justify; text-autospace: none;"><span style="font-size: 12pt; line-height: 150%;">adalah string dengan panjang k, yang dibentuk dari karakter di alfabet di dalam alfabet A. Awalan prefix dari z adalah upa-string w, dengan </span></div><div class="MsoNormal" style="line-height: 150%; margin-bottom: 10.0pt; margin-left: 72.0pt; margin-right: 0cm; margin-top: 12.0pt; mso-layout-grid-align: none; text-align: justify; text-autospace: none; text-indent: 36.0pt;"><span style="font-size: 12pt; line-height: 150%;">w =Z_(k-b),Z_(k-b+1)… Z_k, k Є {1, 2, .., k-1}</span><span style="font-size: 12pt; line-height: 150%;"></span></div><div class="MsoNormal" style="line-height: 150%; margin-bottom: .0001pt; margin-bottom: 0cm; mso-layout-grid-align: none; text-align: justify; text-autospace: none;"><span style="font-size: 12pt; line-height: 150%;">Pinggiran dari z adalah substring r, sehingga</span></div><div class="MsoNormal" style="line-height: 150%; margin-bottom: .0001pt; margin-bottom: 0cm; mso-layout-grid-align: none; text-align: justify; text-autospace: none;"><span style="font-size: 12pt; line-height: 150%;"> r =Z_1 Z_1 Z_3… Z_k, dan r = Z_(k-b),Z_(k-b+1)… Z_k, k Є {1, 2, .., k-1}</span></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhR9eJgRD-Wd8hrJVT7J1z2LlN16Wqw9lLMYW4sVZQR3oIBOsTwJeU3TlOwmiV6zHwsttovtOd5piBPkzfkDS_2hr1Ks5xKkKc8MkWKWHTvyNOKOVcNtTDxTJEsR0oYKgHDY3Oaq3GFDEGY/s1600/kmp.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="115" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhR9eJgRD-Wd8hrJVT7J1z2LlN16Wqw9lLMYW4sVZQR3oIBOsTwJeU3TlOwmiV6zHwsttovtOd5piBPkzfkDS_2hr1Ks5xKkKc8MkWKWHTvyNOKOVcNtTDxTJEsR0oYKgHDY3Oaq3GFDEGY/s320/kmp.JPG" width="320" /></a></div><div class="MsoNormal" style="line-height: 150%; margin-bottom: 0.0001pt; text-align: justify;"><span style="font-size: 12pt; line-height: 150%;"> </span> </div><div class="MsoNormal" style="line-height: 150%; margin-bottom: .0001pt; margin-bottom: 0cm; mso-layout-grid-align: none; text-align: justify; text-autospace: none;"><span style="font-size: 12pt; line-height: 150%;">Algoritma KMP melakukan proses awal terhadap pattern dengan menghitung fungsi pinggiran Dengan adanya fungsi pinggiran ini, maka dapat dicegah pergeseran yang tidak berguna, seperti yang terjadi pada algoritma brute force. Fungsi pinggiran hanya bergantung pada karakter yang ada di dalam pattern, tidak bergantung kepada karakter di dalam teks. Berikut adalah algoritma untuk mencari fungsi pinggiran di dalam pattern.</span></div><div class="MsoListParagraph" style="line-height: 150%; margin-bottom: .0001pt; margin-bottom: 0cm; mso-add-space: auto; mso-layout-grid-align: none; mso-list: l0 level1 lfo1; text-align: justify; text-autospace: none; text-indent: -18.0pt;"><span style="font-size: 12pt; line-height: 150%;">A.<span style="font: 7pt "Times New Roman";"> </span></span> <span style="font-size: 12pt; line-height: 150%;">Procedure Perhitungan Pinggiran Algoritma KMP</span></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhE8PM28TQFBOhyVPsDmiDhR8GjnitD_BvioL7XVjWZT_XKI-Yaf_LCzhDLPmmk8wIX_bYMDDa6ue4Nl8sLlYr07X9tZ64Hvx-HNnt1Y8jawJiqQtVB46feZc4QIMyWZr6PF-Tx-HsPvXyl/s1600/kmp1.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhE8PM28TQFBOhyVPsDmiDhR8GjnitD_BvioL7XVjWZT_XKI-Yaf_LCzhDLPmmk8wIX_bYMDDa6ue4Nl8sLlYr07X9tZ64Hvx-HNnt1Y8jawJiqQtVB46feZc4QIMyWZr6PF-Tx-HsPvXyl/s320/kmp1.JPG" width="278" /></a></div><div class="MsoListParagraph" style="line-height: 150%; margin-bottom: 0.0001pt; text-align: justify; text-indent: -18pt;"><br />
</div><div class="MsoListParagraph" style="line-height: 150%; margin-bottom: 0.0001pt; text-align: justify; text-indent: -18pt;"></div><div class="MsoListParagraph" style="mso-list: l0 level1 lfo1; text-indent: -18.0pt;"><span style="font-size: 12pt; line-height: 115%;">A.<span style="font: 7pt "Times New Roman";"> </span></span><span style="font-size: 12pt; line-height: 115%;">Procedure Algoritma KMP</span></div><div class="MsoListParagraph" style="text-indent: -18pt;"><br />
</div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhx-IGYigHabV6UbweI5BJq878zk7E71oX40kALpGdmBvNUWQJ8xwuebtsHvYx9FF9MJyfQ7wjLhuvFu8MQQV2yXhqKKq0GAmD9byVy540NMuEPF2ZuStJEC2rPN7nrpyT_sP19848AQcfZ/s1600/kmp2.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhx-IGYigHabV6UbweI5BJq878zk7E71oX40kALpGdmBvNUWQJ8xwuebtsHvYx9FF9MJyfQ7wjLhuvFu8MQQV2yXhqKKq0GAmD9byVy540NMuEPF2ZuStJEC2rPN7nrpyT_sP19848AQcfZ/s320/kmp2.JPG" width="199" /></a></div><div class="MsoListParagraph" style="line-height: 150%; margin-bottom: 0.0001pt; text-align: justify; text-indent: -18pt;"><br />
</div><div class="MsoListParagraph" style="line-height: 150%; margin-bottom: 0.0001pt; text-align: justify; text-indent: -18pt;"><br />
</div><div class="MsoNormal" style="line-height: 150%; margin-bottom: 0.0001pt; text-align: justify;"><span style="font-size: 12pt; line-height: 150%;"> Sumber :</span></div><div class="MsoNormal" style="line-height: 150%; margin-bottom: 0.0001pt; text-align: justify;"></div><div class="MsoNormal" style="line-height: 150%;"><span style="font-family: "Arial","sans-serif";">Eko Gunocipto Hartoyo, Yus Gias Vembrina, and Anggia Ferdina Meilana, “Analisis Algoritma Pencarian String (String Matching),” </span><span style="font-size: 12pt; line-height: 150%;">in </span><a href="http://www.informatika.org/%7Erinaldi/Stmik/Makalah/MakalahStmik10.pdf"><span style="font-size: 12pt; line-height: 150%;">www.informatika.org/~rinaldi/Stmik/Makalah/MakalahStmik10.pdf</span></a><cite><span style="font-family: "Calibri","sans-serif"; font-size: 12pt; line-height: 150%;">,</span></cite><cite><span style="font-family: "Calibri","sans-serif";"> </span></cite><span style="font-size: 12pt; line-height: 150%;">Departemen Teknik Informatika, Institut Teknologi Bandung, Bandung, 2007</span></div><div class="MsoNormal" style="line-height: 150%;"><span style="font-size: 12pt; line-height: 150%;"><a href="http://www.informatika.org/%7Erinaldi/Stmik/Makalah/MakalahStmik10.pdf"> Download Paper</a> </span><span style="font-size: 12pt; line-height: 150%;"></span></div><div class="MsoNormal" style="line-height: 150%; margin-bottom: 0.0001pt; text-align: justify;"><span style="font-size: 12pt; line-height: 150%;"></span></div><div class="MsoNormal" style="line-height: 150%; margin-bottom: 0.0001pt; text-align: justify;"><br />
</div>Anthon R. Tampubolonhttp://www.blogger.com/profile/04493652019575515292noreply@blogger.com1