levenshtein function issue

Discussion in 'Ruby' started by Joe Smith, Sep 24, 2010.

  1. Joe Smith

    Joe Smith Guest

    well, I'm trying to get the levenshtein function to work, and it's
    close, but it's not quite giving me the right answer and i have no idea
    why.


    here's the code:
    class Array2D
    def initialize(width, height)
    @data = Array.new(width) { Array.new(height) }
    end
    def [](x, y)
    @data[x][y]
    end
    def []=(x, y, value)
    @data[x][y] = value
    end
    end


    def levenshtein(s, t)
    #include cost?

    m = s.size
    n = t.size

    d = Array2D.new(m+1,n-1)

    for i in 0..m
    d[i,0]=i
    end

    for j in 0..n
    d[0,j]=j
    end


    for j in 1..n
    for i in 1..m
    if(s.eql?(t)) then
    d[i,j]=d[i-1,j-1]
    end

    if not (s.eql?(t)) then
    d[i,j] = [ (d[i-1,j]+1), (d[i,j-1]+1), (d[i-1,j-1]+1)
    ].min
    end
    end
    end


    puts "After:"+ d.inspect

    puts "Ans: "
    return d[m,n]
    end #end func
    =================================================

    when I call it:
    puts "Call to levenshtein():"
    puts levenshtein("string1","2strings")
    =================================================
    and the output...
    here's the output:
    Call to levenshtein():
    After:#<Array2D:0x283ee90 @data=[[0, 1, 2, 3, 4, 5, 6, 7, 8], [1, 1, 2,
    3, 4, 5,
    6, 7, 8], [2, 2, 2, 3, 4, 5, 6, 7, 8], [3, 3, 3, 3, 4, 5, 6, 7, 8], [4,
    4, 4, 4
    , 4, 5, 6, 7, 8], [5, 5, 5, 5, 5, 5, 6, 7, 8], [6, 6, 6, 6, 6, 6, 6, 7,
    8], [7,
    7, 7, 7, 7, 7, 7, 7, 8]]>
    Ans:
    8
    =================================================
    If you check those two strings I tested with at this URL, my resulting
    matrix is wrong (no idea why), and the answer should be 2...
    check it here:
    http://www.miislita.com/searchito/levenshtein-edit-distance.html


    =

    THANK YOU SO MUCH FOR ANY HELP!
    --
    Posted via http://www.ruby-forum.com/.
    Joe Smith, Sep 24, 2010
    #1
    1. Advertising

  2. Joe Smith

    Chris Hulan Guest

    ....
    >
    >   d = Array2D.new(m+1,n-1)


    You have 'n-1' here, but subsequently use indexes up to n.

    cheers
    Chris Hulan, Sep 24, 2010
    #2
    1. Advertising

  3. Joe Smith

    Joe Smith Guest

    Chris Hulan wrote:
    > ...
    >>
    >> � d = Array2D.new(m+1,n-1)

    >
    > You have 'n-1' here, but subsequently use indexes up to n.
    >
    > cheers


    Thanks for the reply. Yes, but when I change that, I just get an
    error... (that's why I had originally changed it)
    --
    Posted via http://www.ruby-forum.com/.
    Joe Smith, Sep 26, 2010
    #3
  4. Joe Smith

    Chris Hulan Guest

    On Sep 26, 12:43 am, Joe Smith <> wrote:
    > Chris Hulan wrote:
    > > ...

    >
    > >> d = Array2D.new(m+1,n-1)

    >
    > > You have 'n-1' here, but subsequently use indexes up to n.

    >
    > > cheers

    >
    > Thanks for the reply.  Yes, but when I change that, I just get an
    > error... (that's why I had originally changed it)
    > --
    > Posted viahttp://www.ruby-forum.com/.


    Looking at the description at http://www.levenshtein.net/ it appears
    that both m and n should be +1
    The strings are then offset to allow indexing from 1. Guess you
    either need to add a character (blank?)
    to the beginning of both strings, or adjust your indexes into s and t
    (the 1st char is the 0th index)

    I'm totally pulling this out of my head, as I don't have Ruby on my
    work computer
    Chris Hulan, Sep 27, 2010
    #4
  5. Joe Smith

    Joe Smith Guest

    Chris Hulan wrote:
    > On Sep 26, 12:43�am, Joe Smith <> wrote:
    >> error... (that's why I had originally changed it)
    >> --
    >> Posted viahttp://www.ruby-forum.com/.

    >
    > Looking at the description at http://www.levenshtein.net/ it appears
    > that both m and n should be +1
    > The strings are then offset to allow indexing from 1. Guess you
    > either need to add a character (blank?)
    > to the beginning of both strings, or adjust your indexes into s and t
    > (the 1st char is the 0th index)
    >
    > I'm totally pulling this out of my head, as I don't have Ruby on my
    > work computer



    Thank you for the reply. Unfortunately, I get the same error when I try
    this :(
    --
    Posted via http://www.ruby-forum.com/.
    Joe Smith, Sep 27, 2010
    #5
  6. Joe Smith

    Chris Hulan Guest

    On Sep 27, 3:37 pm, Joe Smith <> wrote:
    > Chris Hulan wrote:
    > > On Sep 26, 12:43 am, Joe Smith <> wrote:
    > >> error... (that's why I had originally changed it)
    > >> --
    > >> Posted viahttp://www.ruby-forum.com/.

    >
    > > Looking at the description athttp://www.levenshtein.net/it appears
    > > that both m and n should be +1
    > > The strings are then offset to allow indexing from 1.  Guess you
    > > either need to add a character (blank?)
    > > to the beginning of both strings, or adjust your indexes into s and t
    > > (the 1st char is the 0th index)

    >
    > > I'm totally pulling this out of my head, as I don't have Ruby on my
    > > work computer

    >
    > Thank you for the reply.  Unfortunately, I get the same error when I try
    > this :(
    > --
    > Posted viahttp://www.ruby-forum.com/.


    This was bugging me so I installed Ruby and gave it a go.
    You do need to change that 'n-1' to be 'n+1'

    Then in the nested loop you need to use both indexes:
    for j in 1..n
    for i in 1..m
    if(s.eql?(t)) then
    ^this 'i' should be 'j'

    But you still need to adjust the indexes into the strings (i-1 and j-1
    seems to work here)

    cheers
    Chris Hulan, Sep 28, 2010
    #6
  7. Joe Smith

    Joe Smith Guest

    Joe Smith, Sep 29, 2010
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    4
    Views:
    421
  2. jon wayne
    Replies:
    1
    Views:
    375
    benben
    Sep 19, 2005
  3. Gabriel Genellina
    Replies:
    2
    Views:
    368
    Peter Otten
    Feb 14, 2009
  4. John
    Replies:
    11
    Views:
    250
    Dave Bass
    May 25, 2008
  5. Guest

    Text::Levenshtein and utf8 woes

    Guest, Mar 26, 2006, in forum: Perl Misc
    Replies:
    3
    Views:
    239
    Guest
    Mar 26, 2006
Loading...

Share This Page