Skip to content

A fast Python Common substrings of multiple strings library with C++ implementation

Notifications You must be signed in to change notification settings

duongkstn/common_multiple_strings

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

4 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

GitHub

A fast Python Common substrings of multiple strings library with C++ implementation

Having a bunch of strings, can I print some substrings which appear K times ? Can I know which is longest substrings ?

2024 UPDATE:

The project is built as PyPI package: https://pypi.org/project/commonstrings/ . Code for PyPI package is moved to: https://github.com/phamthivan2996/commonstrings

Installing

Make sure Cython is installed properly !

Building from source:

cd python
python setup.py install

Usuage and examples

Step 1. Import the library

from common_multiple_strings import PyCommon_multiple_strings
tree = PyCommon_multiple_strings()  # init

Step 2. Build the data structure

Build from list of str:

tree.from_strings(list_str)

or build from file:

tree.from_path(<path_to_file>)

It is noted that sentences in file are presentened line-by-line. Each line is a sentence.

Sample code:

>>> from common_multiple_strings import PyCommon_multiple_strings
>>> tree = PyCommon_multiple_strings()  # init
>>> list_str = [
       'abc',
       'abcxa',
       'xamnb',
       'yamnc',
       'abcd'
    ]
>>> tree.from_strings(list_str)

Step 3. Query

This library introduces 4 types of query:

a) List some substrings appear TIMES times:

tree.query(times=TIMES)

Ouput is a dictionary with key is an integer K, value is a list of some substrings which appear exactly K times.

Sample code:

>>> print(tree.query(times=(2, None)))
{2: ['amn', 'xa', 'n', 'mn'], 3: ['bc', 'abc'], 4: ['c', 'b'], 5: ['a']}
>>> print(tree.query(times=(3, 3)))
{3: ['bc', 'abc']}

b) Length of the longest substring appears TIMES times:

tree.length_longest_substring(times=TIMES)

Ouput is an integer.

Sample code:

>>> print(tree.length_longest_substring(times=(2, None)))
3

c) Lengths of the longest substrings appear TIMES times:

tree.lengths_longest_substrings(times=TIMES)

Ouput is a dictionary with key is an integer K, value is the length of the longest substring which appear exactly K times.

Sample code:

>>> print(tree.lengths_longest_substrings(times=(2, None)))
{2: 3, 3: 3, 4: 1, 5: 1}

d) List some substrings which have length of L and appear TIMES times:

tree.filter_substrings_by_length(length_input=L, times=TIMES)

Ouput is a dictionary with key is an integer K, value is a list of some substrings which appear exactly K times and have length of L.

Sample code:

>>> print(tree.filter_substrings_by_length(length_input=2, times=(2, None)))
{2: ['xa', 'mn'], 3: ['bc']}
>>> print(tree.filter_substrings_by_length(length_input=10, times=(2, None)))
{}

Some Notes:

- Params:

times, default (None, None) is a tuple represents the minimum and maximum appearances of the desired output.

Query substrings appear exactly N times, then times=(N, N).

Query substrings appear more than N times, then times=(N, None).

Query substrings appear less than N times, then times=(None, N).

Query substrings appear less than N times and more than M times, then times=(M, N).

length_input is an integer, represents the length of substrings

- This library accepts various utf8 characters including punctuations, numbers, upper-case characters, ... For more details, checkout alphabet.cpp file. Thanks coccoc-tokenizer for providing these available lists

- Query a) and d) does not output all possible results, but you can use it for analytic purposes.

Algorithm and Complexity

Data structure suffix tree is the core of this library. It encourages fast query and efficient storing.

If the total length of all input strings are L, then the average complexity should be L * log(L).

References

Algorithm from the lecture of String Algorithms and Algrorithms in Computational Biology - Gusfield

About

A fast Python Common substrings of multiple strings library with C++ implementation

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published