Hirschberg algorithm

[abz89]

somebody have a tried/implemented Hirschberg Algorithm to c#?
i need it :(

to make the program compare the two string and tell where the array index that the different,

thx u

[Christian Binder]

@abz89
Google brought me to this pages:

http://geekswithblogs.net/BVeldhoen/...-.net-2.0.aspx
http://hirschbergcsharp.codeplex.com/

[jkmyoung]

To be honest, based on your earlier posts I would try to understand recursion and tree searches first.


1. One way to look at it: The algorithm is like a tree search except that many of the branches are shared.

2. The algorthim provided is also like filling in a grid, and then finding the best path to the goal.

Figure out how to fill a single cell.
Then figure out how to fill the cell next to it.
Then do that over and over in for loops.

[abz89]

@ChBinder
it can't be downloaded >.<

@jkmyoung
oh dear i've create the programs with needleman-wutsch but it takes so much memory :(

and i've found the hirschberg algo. but i didn't understand the algo :(

[Christian Binder]

@abz89
It can be downloaded!
You've to choose "Source Code"-Menu, not "Download" then click on "3546"-Link and there you'll find the files and a complete download :-)

[abz89]

owh yes.. :D
but the source cannot be tested (run) :(

i'm using vc# 2008 express,, hwa

[Christian Binder]

What happens when you want to run it? Any messages?
Does even compiling doesn't work?

The program expects to be started with command-line-parameters and any file given. I didn't try this program, I just looked a bit through the There are some test-methods inside it which you can maybe use.

[jkmyoung]

You can simplify the space requirements by only storing 2 columns at a time.
Calculate the last column, starting from the bottom. ArrayA

loop{
based on ArrayA calculate the column before, starting from the bottom. ArrayB.
Set ArrayA = ArrayB.
}

[abz89]

@chbinder
yupz, it said some missing object etc...bla bla bla

@jkmyoung
i couldn't understand what you mean, (cause i'm so dumb --_--)

after i've googling, i found the more nice and faster algorithm,
"lazy DPA"

i think,
- needleman or other standard dpa is taking memory and times too much
- hirchberg is fine, but it ate so much time, cause it does double checking

i've been ported the hirchberg to c#, but it cannot processing arrays too long (in my case up to 16k), it said boundary issue or not enough memory resources :(

so i prefer to "lazy dpa",

have somebody tried on c sharp? some source tell that c sharp is slowest when benchmarked with the other languages, such as python, perl, even c++..

i wanna porting the applet (lazy dpa) like this site.
http://drp.id.au/align/2d/AlignDemo.shtml

any help or suggest is so appreciated :)

[jkmyoung]

Regarding space:
Notice how the demo only calculates one row at a time?
Each row is only dependent on itself and the row above.
Eg, once you've calculated row 4, you can throw away the results from row 3. You don't need row 3 to get the results for row 5.

A lazy Hirschberg algorithm is the same except it goes backwards, from the bottom to the top, then right to left.

[abz89]

@jkmyoung

yupz, hirschberg is only calculated the single row and above ones then immedietly flushing the memory with throw the other unnecessary datas..
but it taking two times longer, cause the traceback check will missed the data (which trown before)

sorry that i mistaked, i've been ported the needleman into c sharp..
but it takes error when i use it cause my array data is 16thousand char long,

it said array outbound of index and sometime memory resources issue.

so i need the optimization on needleman, maybe add a pause time?? how can i do that?

if the optimization on needleman not succesed, i'll try hirschberg :)

thx a lot

[jkmyoung]

If you're getting an out of bounds errors, there's probably a small mistake in how you've implemented it. It's hard to tell without seeing the relevant code.

Make sure you're aligning the two strings so that you only need to store only as many cells equal to the shortest string's length..

[abz89]

hmm, here is my codes..

hope u could notify me the error :D
thx a lot

[jkmyoung]

1. Optimization: convertStringToArr
You create a list, and then you copy the list into a int[] array. Why not create the int[] array to begin with?

l.Count equals str.Length
====
2. Error
for(int y=0;y<source.Length;y++)
for(int x=0;x<dest.Length;x++)

These should both be <=
=====
3. Optimization.
You call NeedlemanWunsch.convertStringToArr(s1) twice for each string. Call it once each string, and store the variable.

[abz89]

<quote>
1. Optimization: convertStringToArr
You create a list, and then you copy the list into a int[] array. Why not create the int[] array to begin with?
</quote>

hmm, i will make the GUI for this program with string1 and string2 input fron text box, so i designed it is like this...

<quote>2. Error
for(int y=0;y<source.Length;y++)
for(int x=0;x<dest.Length;x++)

These should both be <=
<quote>

did you mean:

for(int y=0;y<=source.Length;y++)
for(int x=0;x<=dest.Length;x++)

ok..


hi bos, could you fix my codes directly :)
so i can make sure that codes is more efficient and i can learn it

i'm so appreciated with your help :D
thx a lot

[jkmyoung]

Regarding 1.
What I meant is: create the string, that's fine. Don't create the List. In your first for loop set the values of the int array.

--
Unfortunately don't have the time to fix every poster's code, and it would be counter-productive of you to rely on a volunteer service that could disappear any time due to heavy work load on the volunteer's side. If you didn't understand the code at that point, you'd be screwed.

[abz89]

okay, i'll try it..

thx.. :D

[abz89]

i've pre-finished my program with hirscberg :D
thx for everyone ;)

to mod;please lock this thread, if you would..