A Python library written in Rust that searches for substrings quickly using a Suffix Array

Table of Contents

• Table of Contents
• About The Project
  • Built With
  • Performance
    • 500MB File
    • 7500MB File
  • Installation
• Usage
• License
• Contact

About The Project

PySubstringSearch is a library designed to search over an index file for substring patterns. In order to achieve speed and efficiency, the library is written in Rust. For string indexing, the library uses libsais suffix array construction library. The index created consists of the original text and a 32bit suffix array struct. To get around the limitations of the Suffix Array Construction implementation, the library uses a proprietary container protocol to hold the original text and index in chunks of 512MB.

The module implements a method for searching.

• search - Find different entries with the same substring concurrently. Concurrency increases as the index file grows in size with multiple inner chunks.
• search_multiple - same as search but accepts multiple substrings in a single call

Built With

• libsais

Performance

500MB File

Library	Function	Time	#Results	Improvement Factor
ripgrepy	Ripgrepy('google', '500mb').run().as_string.split('\n')	47.2ms	5943	1.0x
PySubstringSearch	reader.search('google')	497µs	5943	95x
ripgrepy	Ripgrepy('text_two', '500mb').run().as_string.split('\n')	44.7ms	159	1.0x
PySubstringSearch	reader.search('text_two')	14.9µs	159	3000x

7500MB File

Library	Function	Time	#Results	Improvement Factor
ripgrepy	Ripgrepy('google', '6000mb').run().as_string.split('\n')	900ms	62834	1.0x
PySubstringSearch	reader.search('google')	10.1ms	62834	89.1x
ripgrepy	Ripgrepy('text_two', '6000mb').run().as_string.split('\n')	820ms	0	1.0x
PySubstringSearch	reader.search('text_two')	200µs	0	4100x

Installation

pip3 install PySubstringSearch

Usage

Create an index

import pysubstringsearch

# creating a new index file
# if a file with this name is already exists, it will be overwritten
writer = pysubstringsearch.Writer(
    index_file_path='output.idx',
)

# adding entries to the new index
writer.add_entry('some short string')
writer.add_entry('another but now a longer string')
writer.add_entry('more text to add')

# adding entries from file lines
writer.add_entries_from_file_lines('input_file.txt')

# making sure the data is dumped to the file
writer.finalize()

Search a substring within an index

import pysubstringsearch

# opening an index file for searching
reader = pysubstringsearch.Reader(
    index_file_path='output.idx',
)

# lookup for a substring
reader.search('short')
>>> ['some short string']

# lookup for a substring
reader.search('string')
>>> ['some short string', 'another but now a longer string']

# lookup for multiple substrings
reader.search_multiple(
    [
        'short',
        'longer',
    ],
)
>>> ['some short string', 'another but now a longer string']

License

Distributed under the MIT License. See LICENSE for more information.

Contact

Gal Ben David - [email protected]

Project Link: https://github.com/Intsights/PySubstringSearch