string2string

The string2string library provides algorithms and tools for various string-to-string problems, including:

• Alignment: Pairwise local alignment (e.g., Smith-Waterman) and global alignment (e.g., Hirschberg).
• Distance: Measuring differences between strings (e.g., Wagner-Fisher for edit distance).
• Search: Lexical search (e.g., Knuth-Morris-Pratt) and semantic search (e.g., Faiss).
• Similarity Analysis: Advanced neural approaches (e.g., BARTScore, BERTScore).
• Metrics: Wrappers for established frameworks like sacreBLEU and ROUGE.

The library is designed for applications in natural-language processing, bioinformatics, and computational social sciences.

Install the string2string library using pip. It is recommended to use Python 3.7 or higher.

pip install string2string

The library provides several interactive tutorials via Google Colab to learn about specific tasks:

• Alignment Tasks and Algorithms
• Distance Tasks and Algorithms
• Search Tasks and Algorithms
• Similarity Tasks and Algorithms
• Semantic Search and Visualization of USPTO Patents (Hands-On)
• Plagiarism Detection of Essays (Hands-On)

The distance module supports both strings and lists of strings. To compute distance at the word level, you can either pass lists of tokens directly to a distance class or use the Tokenizer class from string2string.misc to split text before computing the distance.

from string2string.distance import LevenshteinEditDistance
from string2string.misc import Tokenizer

text1 = "The quick brown fox"
text2 = "The kuack brown fox"

# Option 1: Manual tokenization
tokenizer = Tokenizer(word_delimiter=' ')
tokens1 = tokenizer.tokenize(text1)
tokens2 = tokenizer.tokenize(text2)

edit_dist = LevenshteinEditDistance()
word_level_score = edit_dist.compute(tokens1, tokens2)

# Option 2: Passing lists directly
# word_level_score = edit_dist.compute(['the', 'quick'], ['the', 'kuack'])

To use the string search algorithms and semantic search capabilities, install the package using pip.

# !pip install string2string

This tutorial demonstrates how to use string2string algorithms to detect plagiarism in essays by comparing text at both character and word levels.

Key Metrics

• Character-level edit distance: Measures the number of character-level changes required to transform one text into another.
• Word-level edit distance: Measures the number of word-level changes required to transform one text into another.

Example outputs from the tutorial:

• Character-level edit distance: 3.0
• Word-level edit distance: 2.0

# Note: The provided segment contains the conceptual output of the tutorial rather than the implementation code.
# Edit distance between these two texts at the character level is 3.0
# Edit distance between these two texts at the word level is 2.0

To use the string2string library for plagiarism detection and similarity analysis, install it along with its required dependencies using pip.

!pip install string2string
!pip install scikit-learn
!pip install networkx

The string2string.similarity module provides wrappers for advanced similarity metrics:

• BARTScore(model_name_or_path=...): Computes BARTScore. Use compute(source_sentences, target_sentences, agg='mean', batch_size=4).
• BERTScore(lang=...): Computes BERTScore. Use compute(source_sentences, target_sentences) to get precision, recall, and F1 scores.

from string2string.similarity import BERTScore, BARTScore

# BARTScore
bart_scorer = BARTScore(model_name_or_path='facebook/bart-large-cnn')
score_bart = bart_scorer.compute(source_sentences, target_sentences, agg="mean", batch_size=4)

# BERTScore
bert_scorer = BERTScore(lang="en")
score_bert = bert_scorer.compute(source_sentences, target_sentences)

Use the string2string.distance.LevenshteinEditDistance class to calculate the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one string into another.

from string2string.distance import LevenshteinEditDistance

lev = LevenshteinEditDistance()
# distance = lev.distance(str1, str2)

The string2string.search.NaiveSearch class implements a brute-force string matching algorithm. It checks for the pattern at every possible position in the text.

from string2string.search import NaiveSearch

# Usage depends on the specific implementation of __init__ and search methods
searcher = NaiveSearch()
# result = searcher.search(text, pattern)

The string2string.search.FaissSearch class provides semantic search capabilities using the Faiss library, allowing for similarity-based pattern matching rather than exact character matching.

from string2string.search import FaissSearch

# Usage depends on the specific implementation of __init__ and search methods
searcher = FaissSearch()
# result = searcher.search(text, pattern)