https://fromkk.com/tags/simhash/Recent content in SimHash on KK's Blog (fromkk)Hugoenbebound@gmail.com (KK)bebound@gmail.com (KK)Fri, 17 Apr 2026 17:11:11 +0800https://fromkk.com/posts/near-duplicate-with-simhash/Wed, 04 Dec 2019 00:16:00 +0800bebound@gmail.com (KK)https://fromkk.com/posts/near-duplicate-with-simhash/<p>Before talking about <strong>SimHash</strong>, let&rsquo;s review some other methods which can also identify duplication.</p> <h2 id="longest-common-subsequence--lcs">Longest Common Subsequence(LCS)</h2> <p>This is the algorithm used by <code>diff</code> command. It is also <strong>edit distance</strong> with insertion and deletion as the only two edit operations.</p> <p>This works good for short strings. However, the algorithm&rsquo;s time complexity is \(O(m*n)\), if two strings&rsquo; lengths are \(m\) and \(n\) respectively. So it&rsquo;s not suitable for large corpus. Also, if two corpus consists of same paragraph but the order is not same. LCS treat them as different corpus, and that&rsquo;s not we expected.</p>