Databases
StackOverflow2013
Postsdbo
POApproximate periods of strings - port Python code to F#
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POApproximate periods of strings - port Python code to F#
    primarykey
    data
    text
    <p>Given two strings <code>u</code> and <code>v</code> we can compute the edit distance using the popular Levenshtein algorithm. Using a method introduced in [1] by Sim et al. I was able to compute <code>k</code>-approximate periods of strings in Python with the following code</p> <pre><code>def wagnerFischerTable(a, b): D = [[0]] [D.append([i]) for i, s in enumerate(a, 1)] [D[0].append(j) for j, t in enumerate(b, 1)] for j, s in enumerate(b, 1): for i, t in enumerate(a, 1): if s == t: D[i].append(D[i-1][j-1]) else: D[i].append( min( D[i-1][j] + 1, D[i][j-1] + 1, D[i-1][j-1] +1 ) ) return D def simEtAlTables(s, p): D = [] for i in xrange(len(s)): D.append(wagnerFischerTable(p, s[i:])) return D def approx(s, p): D = simEtAlTables(s, p) t = [0] for i in xrange(1, len(s)+1): cmin = 9000 for h in xrange(0, i): cmin = min( cmin, max(t[h], D[h][-1][i-h]) ) t.append(cmin) return t[len(s)] </code></pre> <p>I wanted to port this to F# however I wasn't successful yet and I am looking forward to get some feedback what might be wrong.</p> <pre><code>let inline min3 x y z = min (min x y) z let wagnerFischerTable (u: string) (v: string) = let m = u.Length let n = v.Length let d = Array2D.create (m + 1) (n + 1) 0 for i = 0 to m do d.[i, 0] &lt;- i for j = 0 to n do d.[0, j] &lt;- j for j = 1 to n do for i = 1 to m do if u.[i-1] = v.[j-1] then d.[i, j] &lt;- d.[i-1, j-1] else d.[i, j] &lt;- min3 (d.[i-1, j ] + 1) // a deletion (d.[i , j-1] + 1) // an insertion (d.[i-1, j-1] + 1) // a substitution d let simEtAlTables (u: string) (v: string) = let rec tabulate n lst = if n &lt;&gt; u.Length then tabulate (n+1) (lst @ [wagnerFischerTable (u.Substring(n)) v]) else lst tabulate 0 [] let approx (u: string) (v: string) = let tables = simEtAlTables u v let rec kApprox i (ks: int list) = if i = u.Length + 1 then ks else let mutable curMin = 9000 for h = 0 to i-1 do curMin &lt;- min curMin (max (ks.Item h) ((tables.Item h).[i-h, v.Length - 1])) kApprox (i+1) (ks @ [curMin]) List.head (List.rev (kApprox 1 [0])) </code></pre> <p>The reason why it "doesn't work" is just that I am getting wrong values. The Python code passes all test cases while the F# code fails every test. I presume that I have errors in the functions <code>simEtAlTables</code> and/or <code>approx</code>. Probably something with the indices, especially accessing the three dimensional list of table in <code>approx</code>.</p> <p>So here are three test cases which should cover different results:</p> <pre><code>Test 1: approx "abcdabcabb" "abc" -&gt; 1 Test 2: approx "abababababab" "ab" -&gt; 0 Test 3: approx "abcdefghijklmn" "xyz" -&gt; 3 </code></pre> <p>[1] <a href="http://www.lirmm.fr/~rivals/ALGOSEQ/DOC/SimApprPeriodsTCS262.pdf" rel="nofollow">http://www.lirmm.fr/~rivals/ALGOSEQ/DOC/SimApprPeriodsTCS262.pdf</a></p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USChristian Ivicevic
    1. USChristian Ivicevic
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POApproximate periods of strings - port Python code to F#
      1. This table or related slice is empty.
      1. VTUpMod
    1. COCare to explain what exactly isn't working? Does it crash? Does it give wrong results? Have you done any work to narrow down where you think the issue is?
      singulars
      1. POApproximate periods of strings - port Python code to F#
      1. USlatkin
    2. CO@latkin: I added some information what might be wrong.
      singulars
      1. POApproximate periods of strings - port Python code to F#
      1. USChristian Ivicevic
    3. COYou say the F# version "fails every test" but you give no hint as to what the tests are. It would be very helpful if you could provide examples of a few of these tests, along with expected and actual output.
      singulars
      1. POApproximate periods of strings - port Python code to F#
      1. USlatkin
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload