string2string: A Modern Python Library for String-to-String Algorithms (2024)

Abstract: We introduce **string2string**, an open-source library that offers a comprehensive suite of efficient algorithms for a broad range of string-to-string problems. It includes traditional algorithmic solutions as well as recent advanced neural approaches to tackle various problems in string alignment, distance measurement, lexical and semantic search, and similarity analysis�along with several helpful visualization tools and metrics to facilitate the interpretation and analysis of these methods. Notable algorithms featured in the library include the Smith-Waterman algorithm for pairwise local alignment, the Hirschberg algorithm for global alignment, the Wagner-Fischer algorithm for edit distance, BARTScore and BERTScore for similarity analysis, the Knuth-Morris-Pratt algorithm for lexical search, and Faiss for semantic search. In addition, it wraps existing efficient and widely-used implementations of certain frameworks and metrics, such as sacreBLEU and ROUGE. Overall, the library aims to provide extensive coverage and increased flexibility in comparison to existing libraries for strings. It can be used for many downstream applications, tasks, and problems in natural-language processing, bioinformatics, and computational social sciences. It is implemented in Python, easily installable via pip, and accessible through a simple API. Source code, documentation, and tutorials are all available on our GitHub page: https://github.com/stanfordnlp/string2string* Documentation: https://string2string.readthedocs.io/en/latest/* GitHub page: https://github.com/stanfordnlp/string2string* Short video: https://drive.google.com/file/d/1IT-pBACDVUoEHewk__5Pz5mU5oAMq5k_/view?usp=sharing

## introduction string-to-string problems have a wide range of applications in various domains and fields, such as natural-language processing (e.g., information extraction, spell checking, and semantic search), computational molecular biology (e.g., dna sequence alignment), programming languages and compilers 1 correspondence to: msuzgun@cs.stanford.edu. the current state of string-to-string processing, alignment, distance, similarity, and search algorithms is marked by a multitude of implementations in many programming languages, such as c++, java, and python, but these implementations are not unified and lack flexibility, modularity, and comprehensive documentation, hindering their accessibility to users. thus, there is a need for a unified platform that combines these functionalities into one accessible and comprehensive system. in this work, we present an open-source library that offers a broad collection of algorithms and techniques for the alignment, manipulation, and evaluation of string-to-string mappings. 2 these problems include measuring the lexical distance between two strings (e.g., under the levenshtein edit distance metric), computing the local or global alignment between two dna sequences (e.g., based on a substitution matrix such as blosum), calculating the semantic similarity between two texts (e.g., using bart-embeddings), and performing efficient semantic search (e.g., via the faiss library by fair @xcite ). the string2string library has been purposefully crafted to prioritize key design principles, including modularity, completeness, efficiency, flexibility, and clarity. as an open-source initiative, the library will continue to grow and adapt to meet the evolving of its user community in the future, and we are committed to ensuring that the library remains a flexible, accessible, and dynamic resource, capable of accommodating the changing landscape of string-to-string problems and tasks. library alignment library local alignment global alignment longest common substring longest common subsequence dynamic time warping search rabin-karp lexical search semantic search with faiss bayer-moore knuth-morris-pratt similarity jaccard similarity jaro(-winkler) similarity lcsubsequence similarity cosine similarity bertscore and bartscore distance levenshtein edit distance hamming distance damerau-levenshtein distance jaccard distance smith-waterman needleman-wunsch hirschberg glove and fasttext word embeddings sentence/document embeddings metrics exact match rouge sbleu miscellaneous visualization of alignments and score matrices @xcite for local alignment, knuth-morris-pratt @xcite for identical string matching (search), and wagner-fisher (wagner and fischer, 1974) for edit distance, as well as recent neural approaches, such as bertscore @xcite and bartscore @xcite for semantic similarity measurements and faiss @xcite for semantic search. the library has been designed to support not only individual strings but also lists of strings so that users can align and compare strings at the token, word, or sentence levels. it further contains visualization features to allow users to visualize alignments and score matrices of strings. ## related work the fields of natural-language processing and machine learning have a long-standing and exemplary tradition of fostering a culture that values opensource tools and libraries. while designing our own string-to-string library, which includes both traditional algorithmic and neural approaches to various problems, we have drawn inspirations from natural language toolkit (nltk; @xcite ), gensim @xcite , opengrm ngram @xcite , stanford corenlp toolkit @xcite , opennmt @xcite , tensor2tensor @xcite , allennlp @xcite , fairseq @xcite , spacy @xcite , stanza @xcite , transformers @xcite , and torch-struct @xcite , among many others. ## overview of algorithms the string2string library offers a rich collection of algorithmic solutions to tackle a wide range of string-to-string problems and tasks. we have clustered these algorithms into four categories: pair-wise alignment, distance measurement, similarity analysis, and search. 3 each category contains a suite of efficient algorithms that are tailored to address specific problems within their respective domain. in what follows, we provide a brief overview of these algorithms, along with the associated problems or tasks they are designed to solve. ## additional features one noteworthy feature of the library is its ability to simplify the use of the glove @xcite or fasttext @xcite word embeddings by enabling users to download and use them with just one line of code. this streamlined process not only saves users time and effort but also eliminates the need for additional installations or complex configurations. by providing this feature, we have sought to make the library more accessible to users and encourage the use of pre-trained word embeddings in various string-to-string tasks and applications, such as measuring the cosine similarity between two words. 6 similarly, users can seamlessly get the averaged or last token embeddings of a piece of text from a pre-trained language model that is hosted on hugging face models @xcite or on their local path in a few lines of code, and we provide both cpu and gpu support for these computations. finally, we note that the library offers various visualization capabilities that allow users to visually inspect the alignment between two strings or the score matrix of the distance or similarity between them. this functionality facilitates the understanding and interpretation of the output of various algorithms and can aid in the selection of the most suitable algorithm for a given task. by incorporating this feature into the library, we aim to enhance the user experience and provide intuitive means of interpreting the outputs. 7 figure 2 shows a simple alignment between two lists of strings, as generated by our library. ## library design principles we have endeavoured to build a comprehensive and easy-to-use platform for numerous string-to-string processing, comparison, manipulation, and search algorithms. we have purposefully structured and organized the library to allow easy customization, functional extension, and modular integration. completeness. the library offers a comprehensive set of classical algorithms as well as neural approaches to tackle a wide range of string-to-string problems. we have intentionally included both efficient and simpler solutions, such as brute-force and memoization-based approaches, where appropriate. by providing multiple solutions to the same problem, the library allows users to compare and contrast the performance of different algorithmic methods. this approach enhances users' understanding of the trade-offs between different algorithmic solutions and helps them appreciate the strengths and limitations of each approach. modularity. to improve the efficiency and maintainability of the codebase, we have adopted a modular design approach that breaks down the code into smaller and self-contained modules. this approach simplifies the process of adding new features and functionalities and modifying existing ones for developers, while also enabling efficient testing, debugging, and overall maintenance of the library. the modular design has allowed us to quickly locate and fix any errors, without disrupting the entire codebase, during development. moreover, this modular approach ensures that the library is scalable and adaptable to future updates and changes, which should enable us to easily improve the library's functionality and expand its use in various tasks and applications moving forward. efficiency. we have taken great care to ensure that the algorithm implementations are efficient both computationally and memory-wise so that they could easily handle large datasets and complex tasks. we provide basic support for process-based parallelism via python's inherent multiprocessing package, as well as joblib. additionally, we provide gpu support for neuralbased approaches, whenever applicable. while we strive to balance efficiency and clarity, we acknowledge that in some cases, trade-offs may exist between the two. in such cases, we have placed greater emphasis on clarity, ensuring that the algorithms are transparent and easy to understand, even at the cost of some efficiency. nonetheless, we be-lieve that the library's overall efficiency, combined with its transparency and comprehensibility, makes it a valuable resource for the community. support for list of strings. the library has been designed to support not only individual strings but also lists of strings-whenever possible, enabling users to align or compare strings at the subword or token level. this feature provides greater flexibility in the library's use cases, as it allows users to analyze and compare more complex data structures beyond only individual strings. by supporting lists of strings, the library can handle a wider range of textual input types and structures. strong typing. the use of strong typing requirements is an essential aspect of the library, as it ensures that the inputs are always consistent and accurate, which is crucial for generating reliable results. by carefully annotating all the arguments of the algorithms used in the library, we have sought to increase the robustness and reliability of the codebase. this approach has helped prevent input-related errors, such as incorrect data type or format, from occurring during execution. accessibility. the library has been implemented in python, a programming language which has been the core of many natural-language processing tools and applications in academia and industry. the string2string library is "pip"-installable and can be integrated into common machine learning and natural-language processing frameworks such as pytorch, tensorflow, and scikit-learn. open-source effort. the library is-and will remain-free and accessible to all users. we hope that this approach will promote community-driven development and encourage collaboration among researchers and developers, enabling them to contribute to and improve the library. ## conclusion we introduced string2string, an open-source library that offers a large collection of algorithms for a broad range of string-to-string problems. the library is implemented in python, hosted on github, and installable via pip. it contains extensive documentation along with several hands-on tutorials to aid users to explore and utilize the library effectively. with the help of the open-source community, we hope to grow and improve the library. we encourage users to feel free to provide us with feedback, report any issues, and propose new features to expand the functionality and scope of the library.