North Pittsburgh Meatpackers

    partial-text-search

    1.0.4 • Public • Published

    Partial Text Search

    A JavaScript library that finds string patterns in a collection of documents. It efficiently finds matches even if the words in each document do not begin with the query pattern.

    The result of each query is a set containing the document indices where the query pattern is contained.

    It uses the suffix array data structure to achieve high performance queries.

    Basic usage

    const PartialTextSearch = require('partial-text-search')
    
    const docs = [
      { title: 'the beatles', summary: 'the beatles were an english rock band formed in liverpool in 1960.' },
      { title: 'blackpink', summary: 'blackpink is a south korean girl group formed by yg entertainment, consisting of members jisoo, jennie, rose, and lisa.' }
    ]
    
    const partialTextSearch = new PartialTextSearch(docs)
    
    partialTextSearch.search('li')
    // Set { 1, 0 }
    
    partialTextSearch.search('liv')
    // Set { 0 }

    Install

    npm install partial-text-search
    

    Advanced

    .searchRanked method

    Instead of a document index set, you can get an object that maps each document to the amount of occurrences found.

    partialTextSearch.searchRanked('a')
    /*
    {
      '0': 42,
      '1': 311,
      '2': 23
    }
    */

    Limit the results

    Add the limit option to get fewer results:

    partialTextSearch.search('aaa')
    // Set { 0, 1, 2, 3, 4, 5 }
    
    partialTextSearch.search('aaa', { limit: 3 })
    // Set { 0, 1, 2 }

    This option is only available for the .search method, and not for .searchRanked.

    The decision of which ones to return or omit is completely arbitrary.

    Ways to index each document

    In order for the suffix array to work properly, it's necessary to reduce each document to a single string before indexing them.

    By default this library will examine each document and extract (from the first level of nesting only) all strings and numbers (converted to strings) and concatenate them to create a single string.

    const doc = {
      title: 'hello world',
      body: 'document content',
      info: {
        year: 2000
      }
    }

    In this example, the resulting string to be indexed for this document will be hello world|document content. Note that the info field was ignored.

    Plus, note that a separator | was added between the two fields. Read more about the separator.

    There are more ways to convert documents to strings, which are described next.

    Index only certain fields from the document

    Extract only certain fields from each document:

    partialTextSearch = new PartialTextSearch(docs, { docToString: ['summary', 'anotherField'] })

    Custom function to convert a document to a string

    You can fully customize the way a document is indexed by providing a function, for example:

    // myDocConversion :: Object -> String
    const myDocConversion = doc => (doc.age * 2) + '||' + doc.name + '||' + doc.surname
    
    partialTextSearch = new PartialTextSearch(docs, { docToString: myDocConversion })

    In this case you must manually add a separator between fields in case you need it.

    Separator

    Before indexing the document list, it's necessary to convert each document to a single string, where some or all fields are concatenated. In order to improve search accuracy, a separator can be added (by default a pipe character, or |) so that it's possible to clearly differentiate one document field from another. This avoids matching a substring that only exists because of the concatenation of two fields, but not in any individual field of the document. Take a look at the following example:

    const docList = [
      { text: 'bana', about: 'na' }
    ]

    When indexing this document, the document needs to be reduced to a single string, and if the resulting string has no separators, then the query banana would match this document, even though the word was not present in any individual field.

    The workaround used by this library to avoid this problem is to insert a separator between document fields.

    Note that not using a separator (or not configuring it properly) doesn't necessarily lead to severe harmful outcomes, but it's nevertheless recommended to configure it.

    If you want to use a character different from |, you can configure a different separator for combining fields into a single string:

    partialTextSearch = new PartialTextSearch(docs, { separator: '/' })

    What if the query patterns and/or the document strings contain the separator being used? The separator is only used as a way to improve accuracy, but it's not part of the actual text (since it's inserted by the library), therefore it shouldn't be used for pattern matching. One way to deal with this problem is to remove the separator from both the document's text (at the time of indexing) and from each query (before calling the search methods). This way, the separator character will only ever appear as a separator, and in no other context:

    const removePipe = x => x.replace(/\|/g, '')
    
    const myDocConversion = doc => removePipe(doc.name) + '|' + removePipe(doc.surname)
    
    const partialTextSearch = new PartialTextSearch(docs, {
      docToString: myDocConversion
    })
    
    const myQuery = 'I love the pipe | symbol'
    
    partialTextSearch.search(removePipe(myQuery))

    Case insensitive support

    Search is case sensitive by design, but there are a few ways to support case insensitive search. The recommended way is to:

    1. At indexing time, convert the strings to lowercase (don't modify the original documents, simply modify the string to index).
    2. Lowercase the query before executing the search.
    const myDocConversion = doc => (doc.title + '|' + doc.text).toLowerCase()
    
    partialTextSearch = new PartialTextSearch(docs, { docToString: myDocConversion })
    
    const someQuery = 'I hAve mIXED cAsEs'
    
    partialTextSearch.search(someQuery.toLowerCase())

    This trick can also be used to remove characters determined to be "useless" like dots, commas, extra whitespace, etc. Remember to apply the same pre-processing to both the documents and the query patterns, otherwise they would not match.

    Contribution

    Your contributions are always welcome and appreciated. Following are the things you can do to contribute to this project.

    1. Report a bug: If you think you have encountered a bug, and I should know about it, feel free to report it in the issues section and I will take care of it.
    2. Request a feature: You can request a feature in the issues section, and if it's viable, it will be added to the development backlog.
    3. Create a pull request: Your pull request will be appreciated by the community. You can get started by picking up any open issues and make a pull request.

    License

    This library is available as open source under the terms of the MIT License.

    Development

    Tests:

    npm run test
    

    Format:

    npm run format
    

    Benchmarks:

    node benchmarks/benchmark.js
    node benchmarks/benchmark2.js 100000
    

    Install

    npm i partial-text-search

    DownloadsWeekly Downloads

    6

    Version

    1.0.4

    License

    MIT

    Unpacked Size

    15.8 kB

    Total Files

    7

    Last publish

    Collaborators

    • felovilches