node-fast-string-search's Introduction

Fast String Search

This module can search substrings in a string by using N-API and boyer-moore-magiclen. The result of benchmark shows that this module is 10 times faster than the indexOf function of a Node.js string.

Initialization

Import this module by using require function.

const fss = require("fast-string-search");

Usage

indexOf

Full text search in a string.

const a = fss.indexOf("coocoocoocoo", "oocoo"); // [1, 4, 7]

You can also set the offset of characters and the number of substrings you want to find.

const a = fss.indexOf(source, pattern, offset, limit);

The default value of offset is 0, and the default value of limit is 1000.

indexOfSkip

Normal text search in a string.

const a = fss.indexOfSkip("coocoocoocoo", "oocoo"); // [1, 7]

lastIndexOf

Full text search from the end of a string.

const a = fss.lastIndexOf("coocoocoocoo", "oocoo"); // [7, 4, 1]

utf16IndexOf/utf16IndexOfSkip/utf16LastIndexOf

const a = fss.utf16IndexOf(Buffer.from("coocoocoocoo", "utf16le"), Buffer.from("oocoo", "utf16le")); // [1, 4, 7]

Tests

To run the test suite, first install the dependencies, then run npm test:

npm install
npm test

Benchmark

To run the benchmark suite, first install the dependencies, then run npm run benchmark:

npm install
npm run benchmark

Here is my result,

Full Text Search
  - 87 milliseconds
  ✓ natively search text(indexOf) (87ms)
  - 7 milliseconds
  ✓ Use FSS to search text

Normal Text Search
  - 35 milliseconds
  ✓ natively search text(indexOf)
  - 46 milliseconds
  ✓ natively search text(RegExp) (46ms)
  - 6 milliseconds
  ✓ Use FSS to search text

License

MIT

node-fast-string-search's People

Contributors

Stargazers

Watchers

node-fast-string-search's Issues

Where is the algorithm

Nice package. How I can see the source code of boyer moore algorithm? In which file it has been?

Is it really faster than `String.indexOf()`?

Hello, nice work!

I tried your benchmark with different sets of inputs, a combination of short, medium and long text or search pattern, i.e.:

short text, short search pattern,
short text, short search pattern,
short text, long search pattern,
medium text, short search pattern,
etc.

My results show that String.indexOf() is faster than this implementation. I read somewhere that the implementation of indexOf in Javascript implements the Boyer-Moore algorithm along with some tweaks based on the inputs.

I think that your test cases in the benchmark are not general enough. You are building a large string with a repeated set of characters. I generated random strings using the crypto module.

Please note that I am not criticizing your work in any way, I just wanted to share my findings after going through your code.

Thanks!

High severity vulnerabilities!

GHSA-4263-q746-94mw

GHSA-hmqg-p8f8-3qrw

Just posting it here to notify you.

Recommend Projects

magiclen / node-fast-string-search Goto Github PK