vishalsodani / ssfst

Subsequential Transducer for Efficient "Dictionary-Based" Text Rewriting

Subsequential Finite State Transducer

Given an input text, produces a new text by applying a fixed set of rewrite rules. The algorithm uses the "leftmost largest match" replacement strategy with skips. No overlap between the replaced parts is possible. The time needed to compute the transducer is linear in the size of the input dictionary. For any text t of length |t| the time it takes to perform a rewrite is O(|t|+|t'|) where t' denotes the resulting output string.

Example Usage

const SSFST = require('ssfst');

const spellingCorrector = new SSFST([
    { input: 'acheive', output: 'achieve'},
    { input: 'arguement', output: 'argument'},
    { input: 'independant', output: 'independent'},
    { input: 'posession', output: 'possession'},
    { input: 'mercy less', output: 'merciless' }
]);

spellingCorrector.process('independant'); // => "independent"
spellingCorrector.process('mercy less arguement'); // => "merciless argument"
spellingCorrector.process('they acheived a lot'); // => "they achieved a lot"

const transducer = new SSFST([
    { input: ' dog ', output: '<a href="https://en.wikipedia.org/wiki/Dog">dog</a>' },
    { input: ' fox ', output: '<a href="https://en.wikipedia.org/wiki/Fox">fox</a>' }
]);

transducer.process('The quick brown fox jumped over the lazy dog.');
/* => The quick brown <a href="https://en.wikipedia.org/wiki/Fox">fox</a> jumped over the lazy <a href="https://en.wikipedia.org/wiki/Dog">dog</a>. */

Requirements

• git
• nodejs v. >= 8.x

Install via NPM

npm i --save ssfst

Clone

git clone https://github.com/deniskyashif/ssfst.git ssfst
cd ssfst
npm i

Run the Example

npm start

Run the Tests

npm test

Code Coverage

npm run cover

References

• "Efficient Dictionary-Based Text Rewriting using Subsequential Transducers" by S. Mihov, K. Schulz
• "Finitely Subsequential Transducers" by C. Allauzen, M. Mohri