/usr/share/doc/libghc-edit-distance-doc/html/src/Text-EditDistance.html is in libghc-edit-distance-doc 0.2.2.1-5build1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | <?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
<head>
<!-- Generated by HsColour, http://code.haskell.org/~malcolm/hscolour/ -->
<title>Text/EditDistance.hs</title>
<link type='text/css' rel='stylesheet' href='hscolour.css' />
</head>
<body>
<pre><a name="line-1"></a><span class='hs-comment'>{-# LANGUAGE PatternGuards #-}</span>
<a name="line-2"></a><span class='hs-comment'>{-# LANGUAGE Safe #-}</span>
<a name="line-3"></a>
<a name="line-4"></a><span class='hs-comment'>----------------------------------------------------------------------------</span>
<a name="line-5"></a><span class='hs-comment'>-- |</span>
<a name="line-6"></a><span class='hs-comment'>-- Module : Text.EditDistance</span>
<a name="line-7"></a><span class='hs-comment'>-- Copyright : (C) 2010-2015 Maximilian Bolingbroke</span>
<a name="line-8"></a><span class='hs-comment'>-- License : BSD-3-Clause (see the file LICENSE)</span>
<a name="line-9"></a><span class='hs-comment'>--</span>
<a name="line-10"></a><span class='hs-comment'>-- Maintainer : Oleg Grenrus <oleg.grenrus@iki.fi></span>
<a name="line-11"></a><span class='hs-comment'>--</span>
<a name="line-12"></a><span class='hs-comment'>-- Computing the edit distances between strings</span>
<a name="line-13"></a><span class='hs-comment'>----------------------------------------------------------------------------</span>
<a name="line-14"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>Text</span><span class='hs-varop'>.</span><span class='hs-conid'>EditDistance</span> <span class='hs-layout'>(</span>
<a name="line-15"></a> <span class='hs-conid'>Costs</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-conid'>EditCosts</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-varid'>defaultEditCosts</span><span class='hs-layout'>,</span>
<a name="line-16"></a> <span class='hs-varid'>levenshteinDistance</span><span class='hs-layout'>,</span> <span class='hs-varid'>restrictedDamerauLevenshteinDistance</span>
<a name="line-17"></a> <span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-18"></a>
<a name="line-19"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Text</span><span class='hs-varop'>.</span><span class='hs-conid'>EditDistance</span><span class='hs-varop'>.</span><span class='hs-conid'>EditCosts</span>
<a name="line-20"></a><span class='hs-keyword'>import</span> <span class='hs-keyword'>qualified</span> <span class='hs-conid'>Text</span><span class='hs-varop'>.</span><span class='hs-conid'>EditDistance</span><span class='hs-varop'>.</span><span class='hs-conid'>Bits</span> <span class='hs-keyword'>as</span> <span class='hs-conid'>Bits</span>
<a name="line-21"></a><span class='hs-keyword'>import</span> <span class='hs-keyword'>qualified</span> <span class='hs-conid'>Text</span><span class='hs-varop'>.</span><span class='hs-conid'>EditDistance</span><span class='hs-varop'>.</span><span class='hs-conid'>SquareSTUArray</span> <span class='hs-keyword'>as</span> <span class='hs-conid'>SquareSTUArray</span>
<a name="line-22"></a>
<a name="line-23"></a><a name="levenshteinDistance"></a><span class='hs-comment'>-- | Find the Levenshtein edit distance between two strings. That is to say, the number of deletion,</span>
<a name="line-24"></a><span class='hs-comment'>-- insertion and substitution operations that are required to make the two strings equal. Note that</span>
<a name="line-25"></a><span class='hs-comment'>-- this algorithm therefore does not make use of the @transpositionCost@ field of the costs. See also:</span>
<a name="line-26"></a><span class='hs-comment'>-- <<a href="http://en.wikipedia.org/wiki/Levenshtein_distance">http://en.wikipedia.org/wiki/Levenshtein_distance</a>>.</span>
<a name="line-27"></a><span class='hs-definition'>levenshteinDistance</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>EditCosts</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Int</span>
<a name="line-28"></a><span class='hs-definition'>levenshteinDistance</span> <span class='hs-varid'>costs</span> <span class='hs-varid'>str1</span> <span class='hs-varid'>str2</span>
<a name="line-29"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>isDefaultEditCosts</span> <span class='hs-varid'>costs</span>
<a name="line-30"></a> <span class='hs-layout'>,</span> <span class='hs-layout'>(</span><span class='hs-varid'>str1_len</span> <span class='hs-varop'><=</span> <span class='hs-num'>64</span><span class='hs-layout'>)</span> <span class='hs-varop'>==</span> <span class='hs-layout'>(</span><span class='hs-varid'>str2_len</span> <span class='hs-varop'><=</span> <span class='hs-num'>64</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- The Integer implementation of the Bits algorithm is quite inefficient, but scales better than the</span>
<a name="line-31"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Bits</span><span class='hs-varop'>.</span><span class='hs-varid'>levenshteinDistanceWithLengths</span> <span class='hs-varid'>str1_len</span> <span class='hs-varid'>str2_len</span> <span class='hs-varid'>str1</span> <span class='hs-varid'>str2</span> <span class='hs-comment'>-- STUArrays if both string lengths > 64. The Word64 implementation is always better, if it is applicable</span>
<a name="line-32"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span>
<a name="line-33"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>SquareSTUArray</span><span class='hs-varop'>.</span><span class='hs-varid'>levenshteinDistanceWithLengths</span> <span class='hs-varid'>costs</span> <span class='hs-varid'>str1_len</span> <span class='hs-varid'>str2_len</span> <span class='hs-varid'>str1</span> <span class='hs-varid'>str2</span> <span class='hs-comment'>-- SquareSTUArray usually beat making more use of the heap with STUArray</span>
<a name="line-34"></a> <span class='hs-keyword'>where</span>
<a name="line-35"></a> <span class='hs-varid'>str1_len</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>length</span> <span class='hs-varid'>str1</span>
<a name="line-36"></a> <span class='hs-varid'>str2_len</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>length</span> <span class='hs-varid'>str2</span>
<a name="line-37"></a>
<a name="line-38"></a><a name="restrictedDamerauLevenshteinDistance"></a><span class='hs-comment'>-- | Find the \"restricted\" Damerau-Levenshtein edit distance between two strings. This algorithm calculates the cost of</span>
<a name="line-39"></a><span class='hs-comment'>-- the so-called optimal string alignment, which does not always equal the appropriate edit distance. The cost of the optimal</span>
<a name="line-40"></a><span class='hs-comment'>-- string alignment is the number of edit operations needed to make the input strings equal under the condition that no substring</span>
<a name="line-41"></a><span class='hs-comment'>-- is edited more than once. See also: <<a href="http://en.wikipedia.org/wiki/Damerau-Levenshtein_distance">http://en.wikipedia.org/wiki/Damerau-Levenshtein_distance</a>>.</span>
<a name="line-42"></a><span class='hs-definition'>restrictedDamerauLevenshteinDistance</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>EditCosts</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Int</span>
<a name="line-43"></a><span class='hs-definition'>restrictedDamerauLevenshteinDistance</span> <span class='hs-varid'>costs</span> <span class='hs-varid'>str1</span> <span class='hs-varid'>str2</span>
<a name="line-44"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>isDefaultEditCosts</span> <span class='hs-varid'>costs</span>
<a name="line-45"></a> <span class='hs-layout'>,</span> <span class='hs-layout'>(</span><span class='hs-varid'>str1_len</span> <span class='hs-varop'><=</span> <span class='hs-num'>64</span><span class='hs-layout'>)</span> <span class='hs-varop'>==</span> <span class='hs-layout'>(</span><span class='hs-varid'>str2_len</span> <span class='hs-varop'><=</span> <span class='hs-num'>64</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- The Integer implementation of the Bits algorithm is quite inefficient, but scales better than the</span>
<a name="line-46"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Bits</span><span class='hs-varop'>.</span><span class='hs-varid'>restrictedDamerauLevenshteinDistanceWithLengths</span> <span class='hs-varid'>str1_len</span> <span class='hs-varid'>str2_len</span> <span class='hs-varid'>str1</span> <span class='hs-varid'>str2</span> <span class='hs-comment'>-- STUArrays if both string lengths > 64. The Word64 implementation is always better, if it is applicable</span>
<a name="line-47"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span>
<a name="line-48"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>SquareSTUArray</span><span class='hs-varop'>.</span><span class='hs-varid'>restrictedDamerauLevenshteinDistanceWithLengths</span> <span class='hs-varid'>costs</span> <span class='hs-varid'>str1_len</span> <span class='hs-varid'>str2_len</span> <span class='hs-varid'>str1</span> <span class='hs-varid'>str2</span> <span class='hs-comment'>-- SquareSTUArray usually beat making more use of the heap with STUArray</span>
<a name="line-49"></a> <span class='hs-keyword'>where</span>
<a name="line-50"></a> <span class='hs-varid'>str1_len</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>length</span> <span class='hs-varid'>str1</span>
<a name="line-51"></a> <span class='hs-varid'>str2_len</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>length</span> <span class='hs-varid'>str2</span>
</pre></body>
</html>
|