StringMatching - Algoviz Wiki

PartOfCollection

Works

Yes

Description

This example illustrates the difference of two string matching algorithms, the Knuth-Morris-Pratt algorithm and the Boyer-Moore algorithm.

Evaluation

After slight technical problems of getting the example to work it illustrated the algorithms rather clearly. The graphical presentation is sufficient and the program run flows in a reasonable speed. What I was left a bit bothered by was that the example did not provide any information on the algorithms itself except how they seem to work as they are tried. A pseudo-code representation (which could be followed the same time) or at least some textual explanation could be useful as well as the possibility to run the example step-by-step. Now this example doesn't really support self-studying but can well be used with a teacher explaining in the same time. The "Algorithm information: Skip Function" -part in the top is rather confusing and its purpose was not clear.

Lecture Aid

Screenshots

Videos

References

First Visited

2007

Last Visited

2008

Last Updated

2000

Topic

Community

Average rating:	2.0
Your rating:	You must be logged in to Rate.

http://www.animal.ahrgr.de/showAnimationDetails.php3?anim=52; http://www.animal.ahrgr.de/showAnimationDetails.php3?anim=53; http://www.animal.ahrgr.de/showAnimationDetails.php3?anim=54

Edit

You may edit this entry if you have an account.

Animal - String Matching

Recommendation

Has Potential

Link

Delivery Method

Animal Animation

License

Non-Commercial

Language

English; German

Author

Guido Rössling

Institution

TU Darmstadt, Darmstadt, Germany

Project

Animal

PartOfProject

Works

Yes

Description

Site includes a series of three string mating presentations. The first is an example of the "brute force" string matching algorithm. Next is an example for setting up the "next" array in KMP string matching. The third shows an illustration of KMP. Presentation is in the form of a slideshow, as for class notes.

Evaluation

Generally a good presentation. It is especially welcome to see a clear explanation for how the "next" table is built. The KMP example is a little hard to follow independently, but possible. It should work well as a lecture aid.

Animation; Step Control; Canned Data

Lecture Aid; Self Study

Screenshots

Videos

References

For detailed instructions on how to install Animal and run Animal AVs, see: http://www.algoanim.info/Animal2/?q=node/290. Once you have installed the Animal .jar file and downloaded/unpacked the .zip file of Animal animations, you are now ready to run Animal. Run the .jar file to start Animal. Then go to the "Open" menu item, and browse to where you put the animal animations you got in the .zip file. Pick this AV from the list. You can then step through the animation, or use "kiosk mode" to have the steps fed to you at a constant pace.

First Visited

2007-07-21

Last Visited

2010-02-05

Last Updated

1999-04-22

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://research.cs.vt.edu/AVresearch/Swan/

Edit

You may edit this entry if you have an account.

Swan - KMP String Matching

Recommendation

Has Potential

Link

Delivery Method

Windows Application

License

GPL

Language

English

Author

Jeff Nielsen; Jun Yang; Cliff Shaffer

Institution

Virginia Tech

Project

Swan

PartOfProject

Works

Yes

Description

Demonstrates the Knuth-Morris-Pratt algorithm. Given a string from an input file, the user enters a search pattern. The AV then steps through the process of building the match table and searching the string for matches.

Evaluation

While the stepping process demonstrates what is happening, it will only make sense to somebody who has already read a description of the algorithm and is looking to see a demonstration to help them understand the details.

Step Control; Canned Data

Lecture Aid; Teaching the Concept

Screenshots

Videos

References

First Visited

2006-11-08

Last Visited

2008-06-27

Last Updated

1996

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cse.iitk.ac.in/users/dsrkg/cs210/html/strings.html

Edit

You may edit this entry if you have an account.

Ghosh - String Matching

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

R. K. Ghosh

Institution

Indian Institute of Technology, Kanpur

Project

Ghosh's Collection

PartOfCollection

Works

Yes

Description

A collection of four string matching algorithms, including "naive", Boyer-Moore, Knuth-Morris-Pratt, Robin-Karp. Users can enter their own strings and patterns to match, or choose default data. Takes the user step-by-step through the process.

Evaluation

The color scheme is rather bright. The controls are reasonably clear. The presentation of the algorithms needs some work to become more clear. Each step of the process has an associated animation, with no speed control. It tends to be too slow, but at the same time, the explanatory messages get overwritten and the user doesn't have control of their pacing, so doesn't have a chance to absorb what is happening.

Canned Data; User Data; Animation; Step Control

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2006-11-06

Last Visited

2008-07-15

Last Updated

2001-08-12

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.eecs.wsu.edu/~holder/courses/cse2320/lectures/applets/string/test.html

Edit

You may edit this entry if you have an account.

UTA String

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Language

English

Author

Lawrence Holder

Institution

University of Texas, Arlington

Project

StandAlone

StandAlone

Works

Yes

Description

This tool compares the performance of brute force, Knuth-Morris-Pratt and Boyer-Moore string matching algorithms.

Evaluation

This visualization tool has very minimal information and is not very good example of string matching visualization tools out there on the web. The tool compares brute force, Knuth-Morris-Pratt and Boyer-Moore algorithms on the basis of time they take for any given set of data. However in this case given set of data is fixed (one set of predefined string of numbers and a pattern string). You can start animation by clicking the pattern string which then stops at the finish. It does not highlight matched pattern or any other points of interests. Also there is no explanation about various algorithms. It is more like a black box which in the end tells you how finished first. I would say it is practically unusable until or unless you use it for performance comparison purpose only.

Comparison

Screenshots

Videos

References

First Visited

2007

Last Visited

Last Updated

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://alvie.algoritmica.org/

Edit

You may edit this entry if you have an account.

ALVIE - Longest Common Subsequence

Recommendation

Unrated

Link

Delivery Method

Java Application

License

By Request

Language

English

Author

Pilu Crescenzi

Institution

University of Florence

Project

ALVIE

PartOfProject

Works

Yes

Description

Walkthrough showing an algorithm to determine the longest common subsequence between two strings.

Evaluation

Simple-to-use user interface for walking through the example. Simply open up the AV (see directions below) and step through the example with pseudo-code. As you go through the example, you are directed to the corresponding line in the pseudocode and given a line or two of explanation in the message window. Attractive layout of the data, including colors.

Step Control; Canned Data

http://sites.google.com/site/alviehomepage/alvie3/downoads/longestCommonSequence.swf

Lecture Aid; Self Study

Screenshots

Videos

References

Download and unzip the ALVIE system from the website. Double click on the .jar file. Within the ALVIE pane (not the GRIND pane), click on the "eye" icon (third icon from the left in the toolbar) to get a list of algorithms from which select the AV that you want. Once selected, click OK and step through the AV with the arrow icons.

First Visited

2010-01-29

Last Visited

2010-01-29

Last Updated

2009-12-20

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.