Skip to content

Latest commit

 

History

History
45 lines (30 loc) · 2.15 KB

README.md

File metadata and controls

45 lines (30 loc) · 2.15 KB
Raw

Spellchecker (Levenshtein)

Demo of a spellchecker using Levenshtein Distances to correct the user's input while suggesting new words.

This project implements the three most common ways of computing the edit distance between words:

  1. Recursive method: inefficient and slowest way.
  2. Wagner–Fischer algorithm (full-matrix variant): enhancement over the recursive method using a matrix to cache repetitive computations.
  3. Wagner–Fischer algorithm (single-row variant): further enhancement over the matrix method storing only the most significant data at a time.

The distance between words is later used to compare a given input against a dictionary and make suggestions, in the same manner most modern text processors do. Word comparisons are run in parallel for enhanced performance.

Compiling and running

Getting the executable

  • Build from source:

    1. Run cmake . inside the project folder to generate the Makefile.
    2. Run make inside the project folder to generate the binaries.
    3. Run the executable named spellchecker.

  • Or download the linux executable from the bin folder.

Program usage

The executable accepts several arguments:

  • -h, --help: Show the program's help menu.
  • -d, --dict: Relative path of the dictionary to be used. Defaults to dictionary.txt.
  • -s, --suggestions: Number of words suggested by the spellchecker. Defaults to 5.

Once running, select the algorithm you want the spellchecker to use and start entering words to receive feedback.

References