GSoC/GCI Archive
Google Code-in 2011 Parrot Foundation

Implement Levenshtein Distance Algorithm in Winxed for Rosella

completed by: Nagato Yuki

mentors: Andrew Whitworth

Task Description

The Parrot repository contains an implementation of the Levenshtein Distance algorithm written in PIR (examples/pir/levenshtein.pir). The Rosella project would like to have an implementation of this algorithm as part of it's String library.

Write an implementation of the Levenshtein Distance algorithm in Winxed for Rosella. You may either attempt to do a line-by-line translation of the existing PIR implementation or you may write your own from the ground up.

Add a "difference(string a, string b)" function to src/string/String.winxed. It should return an integer for the number of differences between the two strings. Add tests for the new function to t/string/String.t, following existing formatting guidelines. Add a short description of the new function to the "libraries/string.md" documentation file in the gh-pages branch.

Steps To Complete This Task

  1. Create a fork of Rosella.git on github.com
  2. Add the new function and tests on the "master" branch. Build Rosella and run tests to verify that nothing is broken.
  3. Open a pull request to pull your changes to Rosella master
  4. Checkout the gh-pages branch. Add documentation to libraries/string.md
  5. Open a second pull request to pull your changes into the "gh-pages" branch of Rosella

Benefits

  1. The Levenshtein distance algorithm is extremely useful for comparing two strings for similarity, and finds many real-world uses.

Requirements

  1. Knowledge of Winxed or related languages (C++, Java, JavaScript)

Additional Links