npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

string-algorithms

v1.0.31

Published

Linear-time string search and comparison algorithms.

Downloads

2,515

Readme

String Algorithms

Build Status Coverage Status

Features

This package implements a collection of linear-time and linear-space string algorithms that are often used when implementing more advanced searching, sorting and indexing algorithms. The algorithms all accept and properly handle 16-bit Unicode strings.

The algorithms implemented are:

Note: While the algorithms provided here are linear-time implementations, they are still outperformed by readily available C/C++ implementations.

Also note that although these implementations are O(n), linear time does not automatically beat O(n log(n)) all the time. More efficient implementations that are O(n log(n)) may in fact be faster in practice in many situations. To see that, consider that log2(n) grows very slowly. For example log2(100,000) is approximately 16.6. The linear-time longest common substring implementation makes many linear passes through the input string, quite possibly more than 16 in total. So if there exists an O(n log(n)) implementation that can do everything it needs to do in just one pass through the input, it would already come out ahead of the linear time implementation for n less than or equal to 100,000.

Due to limitations of Node.js, the maximum string size is currently limited too by the maximum heap size which is currently just shy of 2GB--and the actual longest string that can be handled by the multiple longest common substring algorithm will be sevaral factors shorter than the maximum heap size.

Examples

Longest Common Substring of Multiple Strings

Find the longest common substring:

import { longestCommonSubstring } from 'string-algorithms';

const strings = [
  '12apple',
  '3apple4',
  'apple56'
];

console.log(longestCommonSubstring(strings));

produces the output apple.

Run the example.

Suffix Array

Find the suffix array of mississippi:

import { suffixArray } from 'string-algorithms';

console.log(suffixArray('mississippi'));

produces the output

[
  11, //  $
  10, // i
  7, //  ippi
  4, //  issippi
  1, //  ississippi
  0, //  mississippi
  9, //  pi
  8, //  ppi
  6, //  sippi
  3, //  sissippi
  5, //  ssippi
  2 //  ssissippi
]

Run the example.

Radix Sort

Given an array with arrays of integers:

import { radixSort } from 'string-algorithms';

const integers = [
  [-9,  4,  0],
  [ 4, -2,  3],
  [ 4,  2, -1],
  [ 1,  0,  6],
  [-4, -2, -5],
  [ 4,  6,  8],
];

const result = radixSort(integers);

/*
[
  [-9,  4,  0],
  [-4, -2, -5],
  [ 1,  0,  6],
  [ 4, -2,  3],
  [ 4,  2, -1],
  [ 4,  6,  8],
];
*/

Run the example.

Given an array of strings that are all the same length, and a function that converts each string to an array of char codes:

const strings = [
  'image',
  'mania',
  'genom',
  'mango'
];

const result = radixSort(strings, s => s.split('').map(c => c.charCodeAt(0)));

/*
[
  'genom',
  'image',
  'mango',
  'mania'
]
*/

Run the example.

Install

npm install --save string-algorithms

API

function search(text, term)

Finds all instances of term in the given text.

text is the string to be searched.

term is the substring to search for.

Returns an array with the start index of all occurrences of term in text.

Note:

function radixSort(entries, getEntry)

Radix sorts an array of entries. If getEntry is not given, then entries is assumed to contain an array of arrays where each sub-array is of the same length. If getEntry is given, then the entries may be of any type, but getEntry must return an array of the same length corresponding to each given entry.

entries is an array with entries to be radix sorted.

getEntry is an optional function for retrieving each entry as an array. For example, entries may contain arrays that are all 4 elements long, but only the last three elements should be considered for sorting. In that case, getEntry could be entry => entry.slice(1).

Returns a new array with the sorted entries.

Note: Although this is a linear-time sort algorithm, it requires input to be of a uniform length (arrays with k entries, strings with at most k characters, digits with at most k digits and so on). The constant overhead is also pretty big, so for something as simple as sorting integers, a fast O(n * log(n)) implementation will probably beat radix sorting even for pretty big n.

function suffixArray(s, terminator)

Calculates the suffix array for the given string and an optional terminator code which must be negative.

s is the string or array of character codes to compute the suffix array for.

terminator is an optional negative terminator code. The terminator code must not be present anywhere in s.

Returns an array with the sorted suffixes of s.

function longestCommonPrefix(sequence, suffixArray)

Calculates the longest common prefix from a suffix array in linear time.

sequence is a sequence of character codes.

suffixArray is the suffix array corresponding to sequence.

Returns an array indicating the height of the shared prefix between adjecent suffix array entries.

function longestCommonSubstring(strings, indexMap)

Finds the longest common substring(s) in the set of given strings. If there are multiple substrings that all share the longest length, then all such substrings are returned. O(n + k) or O(n + k log(k)) depending on the selected string indexing strategy.

strings is an array of strings.

indexMap is the optional string indexing map strategy. If given a string, it must be one of 'log' or 'linear'. Otherwise it must be an object that derives from StringIndexMap. The default value is 'log'.

Returns an array with the longest common substrings(s).

class StringIndexMap

Maps the position of strings s1 ... sK when concatenated into one string. Concrete implementations provide different compromises between O(1) and O(log(k)) lookup times versus O(n) and O(k) space requirements. Extend this class to implement custom mappings from string positions to substring indices with different runtime/space tradeoffs than the two pre-defined implementations.

function add(length)

Adds a substring with the given length.

length is the length of the substring.

Returns the current total length of all substrings.

lookup(position)

Looks up the substring corresponding to the given position in the concatenated string.

position is the position in the concatenated string

Returns the index of the substring that contains the given position.

toString()

Returns a string representation of the string index map.

Contributing

Contributions welcome; Please submit all pull requests against the master branch. If your pull request contains JavaScript patches or features, you should include relevant unit tests. Please check the Contributing Guidelines for more details. Thanks!

Author

Kim Burgaard <[email protected]>.

Made in Sunny California with love and sustainably harvested coffee.

License

MIT