Jeni's Musings

I did wonder about that, but I can’t for the life of me make the template version do any better. Here’s what I’ve been trying: maybe someone else can get Saxon to recognise the tail recursion…

<xsl:template name="my:LevenshteinDistanceB" as="xs:integer">
  <xsl:param name="string1" as="xs:string" select="''" />
  <xsl:param name="string2" as="xs:string" select="''" />
  <xsl:param name="chars1" as="xs:integer*" 
    select="string-to-codepoints($string1)" />
  <xsl:param name="chars2" as="xs:integer*" 
    select="string-to-codepoints($string2)" />
  <xsl:param name="i1" as="xs:integer" select="1" />
  <xsl:param name="i2" as="xs:integer" select="1" />
  <xsl:param name="lastRow" as="xs:integer+" 
    select="for $p in (0 to string-length($string1)) return $p" />
  <xsl:param name="thisRow" as="xs:integer+" select="1" />
  <xsl:choose>
    <xsl:when test="count($chars1) = 0 or $i2 > count($chars2)">
      <xsl:sequence select="$lastRow[last()]" />
    </xsl:when>
    <xsl:otherwise>
      <xsl:variable name="cost" 
        select="min(($lastRow[$i1 + 1] + 1,
                     $thisRow[last()] + 1,
                     $lastRow[$i1] +
                       (if ($chars1[$i1] eq $chars2[$i2]) then 0 else 1)))" />
      <xsl:variable name="nextRow" as="xs:boolean" 
        select="$i1 = count($chars1)" />
      <xsl:call-template name="my:LevenshteinDistanceB">
        <xsl:with-param name="chars1" select="$chars1" />
        <xsl:with-param name="chars2" select="$chars2" />
        <xsl:with-param name="i1" 
          select="if ($nextRow) then 1 else ($i1 + 1)" />
        <xsl:with-param name="i2" 
          select="if ($nextRow) then ($i2 + 1) else $i2" />
        <xsl:with-param name="lastRow" 
          select="if ($nextRow) then ($thisRow, $cost) else $lastRow" />
        <xsl:with-param name="thisRow" 
          select="if ($nextRow) then $i2 + 1 else ($thisRow, $cost)" />
      </xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

Actually, this version made me think of another time when templates are nicer than functions: when you have lots of parameters, it’s helpful to be able to pass them by name rather than position.

I seem to remember Dimitre raising a similar comment on the saxon list a while ago?

Yes, I did. From Dr. Kay’s response I got the impression that in order for Saxon to recognize TR in functions, the function should not produce any output until the very end. That means,collect the outpu in a variable and pass it along down the calls.

Definitely, absolutey, any improvement in Saxon’s treatment of TR in functions would be extremely appreciated. Otherwise, having to convert the code to DVC can sometimes be very challenging.

Cheers,

Dimitre

Thanks George. You’ll see that I’ve adopted your suggestion (my apologies to anyone reading while I was experimenting).

Here’s the XQuery implementation of the dynamic programming version. (I’ve used the same style as you, in particular omitting variable declarations where they’re unnecessary.)

declare function local:levB($arg1 as xs:string, 
                            $arg2 as xs:string) as xs:decimal
{
  local:levB(string-to-codepoints($arg1), 
             string-to-codepoints($arg2),
             1, 1,
             for $p in (0 to string-length($arg1)) return $p,
             1)
}

declare function local:levB($chars1 as xs:integer*,
                            $chars2 as xs:integer*,
                            $i1 as xs:integer,
                            $i2 as xs:integer,
                            $lastRow as xs:integer+,
                            $thisRow as xs:integer+)
  as xs:decimal
{
  if ($i1 > count($chars1)) then
    if ($i2 = count($chars2)) then $thisRow[last()] else
    local:levB($chars1, $chars2, 
               1, $i2 + 1, $thisRow, $i2 + 1) else
  local:levB($chars1, $chars2, $i1 + 1, $i2, $lastRow,
    ($thisRow,
     min((
       $lastRow[$i1 + 1] + 1,
       $thisRow[last()] + 1,
       $lastRow[$i1] + 
         (if ($chars1[$i1] = $chars2[$i2]) then 0 else 1)
     ))
    )
  )
};

Unsurprisingly, it gives exactly the same “infinite recursion” error with Saxon when comparing strings over 20 characters in length.

I’ll leave XSLT vs. XQuery debates for another time…

Oh well here’s the O(M*N) one, pretty similar to yours I think, and hits the same limits, I don’t think it should really as it’s tail recursive. Of course, normally I would have fully documented the code, but as I was so hurt by your remarks in the regex post, this is just unadorned xslt….

<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:xs="http://www.w3.org/2001/XMLSchema"
xmlns:d="data:,dpc">

  <xsl:param name="debug"/>

  <xsl:template name="test">

    <xsl:sequence select="d:levenshteintest('0123456789001234567890','01234567890ABCDEFGHIJ')"/>
    <xsl:sequence select="d:levenshteintest('GUMBO','GAMBOL')"/>
    <xsl:sequence select="d:levenshteintest('GUMBO','GAMBOL')"/>

    <xsl:sequence select="d:levenshteintest('GUMBO','')"/>
    <xsl:sequence select="d:levenshteintest('','GAMBOL')"/>

  </xsl:template>


  <xsl:function name="d:levenshteintest">
    <xsl:param name="s" as="xs:string"/>
    <xsl:param name="t" as="xs:string"/>
    <xsl:text>&#10;distance( "</xsl:text>
    <xsl:value-of select="$s"/>
    <xsl:text>" , "</xsl:text>
    <xsl:value-of select="$t"/>
    <xsl:text>" ) = </xsl:text>
    <xsl:value-of select="d:levenshtein($s,$t)"/>
  </xsl:function>


  <xsl:function name="d:levenshtein">
    <xsl:param name="s" as="xs:string"/>
    <xsl:param name="t" as="xs:string"/>
    <xsl:variable name="n" select="string-length($s)"/>
    <xsl:variable name="m" select="string-length($t)"/>
    <xsl:variable name="ss" select="string-to-codepoints($s)"/>
    <xsl:variable name="tt" select="string-to-codepoints($t)"/>
    <xsl:sequence
    select="if ($n=0) 
        then
        $m
        else
                if ($m=0)
                then
                $n
                else
        d:levenshtein2(
        $m,
        $n,
        (for $i in (0 to $n) return $i,
                 for $j in (1 to $m) return 
                   ($j, for $i in (1 to $n) return 
                      (if($ss[$i]=$tt[$j]) then 0 else 1))),
        $n+3)
"/>
  </xsl:function>

  <xsl:function name="d:levenshtein2">
    <xsl:param name="m" as="xs:integer"/>
    <xsl:param name="n" as="xs:integer"/>
    <xsl:param name="a" as="xs:integer+"/>
    <xsl:param name="p" as="xs:integer"/>
<xsl:if test="$debug='yes'">
<xsl:value-of select="$m,$n"/>
======================================
<xsl:for-each select="0 to ($m)">
<xsl:text>&#10;</xsl:text>
<xsl:value-of select="for $x in subsequence($a,1+ . * ($n+1),$n+1) return format-number($x,'00')"/>
</xsl:for-each>
======================================
</xsl:if>
<xsl:choose>
  <xsl:when test="$p=2+($n+1)*($m+1)">
    <xsl:sequence select="$a[last()]"/>
  </xsl:when>
  <xsl:otherwise>
  <xsl:sequence select="d:levenshtein2($m,$n,
            ($a[position()&lt;$p],  
                        min((
$a[position()=$p - ($n+1)]+1,
$a[position()=$p - 1] + 1,
$a[position()=$p - ($n+2)]+$a[position()=$p]
                        )),
            $a[position()&gt;$p]),
            if($p mod ($n+1) = 0) then $p+2 else $p+1)
    "/>
  </xsl:otherwise>
</xsl:choose>
  </xsl:function>




</xsl:stylesheet>

$  saxon8 -it test levenshtein.xsl 

distance( "0123456789001234567890" , "01234567890ABCDEFGHIJ" ) = 11
distance( "GUMBO" , "GAMBOL" ) = 2
distance( "GUMBO" , "GAMBOL" ) = 2
distance( "GUMBO" , "" ) = 5
distance( "" , "GAMBOL" ) = 6

David