aho_corasick 1.1.0

  • Readme
  • Changelog
  • Example
  • Installing
  • 74

Implementation of the Aho-Corasick algorithm for finding words in a text. The Aho-Corasick algorithm is especially fast if you have a large list of words that might have some matches in your text.

Usage #

You can either search for all or for the first match with the optional flag to search for the first, but longest match.

import 'package:aho_corasick/aho_corasick.dart';

main() {
  final aho = AhoCorasick.fromWordList(['abc', 'bcd', 'bcde']);
  final results = aho.matches('search in abcd');
  print(results
      .map((match) => 'found ${match.word} at ${match.startIndex}')
      .join('\n'));
  // > found abc at 10
  // > found bcd at 11

  final longest = aho.firstMatch('search bcde', longest: true);
  print(longest.word); // > bcde
}

Some Technical Details #

It creates a state machine for all the words with a failure mechanism, if a word does not match it can easily find other words whose prefix was just read by the algorithm. Therefore it has a initialization that is proportional to the number of words and the characters used. The Search phase is usually linear for "normal texts". Edge cases like "only one character" can lead to a quadratic time complexity, but that is only because the number of results can be quadratic in the length of the text.

More information at: https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm

Sadly the original paper is not open access. But there is ample material elsewhere.

1.0.1 #

  • Fixed linter issues and updated description.

1.0.0 #

  • Initial version of the Aho-Corasick algorithm with a basic set of tests and an example.

example/aho_corasick_example.dart

import 'package:aho_corasick/aho_corasick.dart';

main() {
  final aho = AhoCorasick.fromWordList(['abc', 'bcd', 'bcde']);
  final results = aho.matches('search in abcd');
  print(results
      .map((match) => 'found ${match.word} at ${match.startIndex}')
      .join('\n'));

  final longest = aho.firstMatch('bcde', longest: true);
  print(longest.word);
}

Use this package as a library

1. Depend on it

Add this to your package's pubspec.yaml file:


dependencies:
  aho_corasick: ^1.1.0

2. Install it

You can install packages from the command line:

with pub:


$ pub get

with Flutter:


$ flutter pub get

Alternatively, your editor might support pub get or flutter pub get. Check the docs for your editor to learn more.

3. Import it

Now in your Dart code, you can use:


import 'package:aho_corasick/aho_corasick.dart';
  
Popularity:
Describes how popular the package is relative to other packages. [more]
48
Health:
Code health derived from static analysis. [more]
100
Maintenance:
Reflects how tidy and up-to-date the package is. [more]
100
Overall:
Weighted score of the above. [more]
74
Learn more about scoring.

We analyzed this package on Oct 21, 2019, and provided a score, details, and suggestions below. Analysis was completed with status completed using:

  • Dart: 2.5.1
  • pana: 0.12.21

Platforms

Detected platforms: Flutter, web, other

No platform restriction found in primary library package:aho_corasick/aho_corasick.dart.

Health suggestions

Format lib/src/aho_corasick.dart.

Run dartfmt to format lib/src/aho_corasick.dart.

Dependencies

Package Constraint Resolved Available
Direct dependencies
Dart SDK >=2.1.0 <3.0.0
meta ^1.1.6 1.1.7
Dev dependencies
pedantic ^1.0.0
test ^1.0.0