DEV Community: Essi Alizadeh

Python’s itertools: A Hidden Gem for Efficient Looping

Essi Alizadeh — Thu, 08 Jun 2023 04:23:58 +0000

Outline

Introduction
What is an iterator in Python?
- How is an iterator defined in Python?
A deep dive into itertools library
- Infinite Iterators
- count(start, step)
- cycle(iterable)
  - More advanced example: Cycle through a list
- repeat(object, times)
- Combinatoric Iterators
- product(iterable, repeat)
- permutations(iterable, r)
- combinations(iterable, r)
- Terminating Iterators
- accumulate(iterable, func)
- groupby(iterable, key)
- chain(iterables)
Conclusion
References

Introduction

The itertools [1] module in Python is a powerful tool that provides a set of functions for creating iterators to support efficient looping and handling of sequences.
It's part of Python's standard library, meaning it's available in every Python installation.

Let's first talk about what a Python iterator is before diving into the itertools functions.

What is an iterator in Python?

An iterator is a Python object that can be looped over, or iterated.
Data containers may be abstracted in order to get access to and perform operations on their contents without revealing their internal representation.

Python has several built-in functions and objects that return iterators.
Some of the more frequent ones are as follows:

Basic data types: Lists, tuples, strings, and dictionaries,
Built-in functions: range(), enumerate(), zip()

How is an iterator defined in Python?

An iterator object must implement two special methods: __iter__() and __next__(), collectively known as the iterator protocol [2].

The __iter__() method returns the iterator object itself, and is required for your object to be used in any iteration context, such as a for loop.
The __next__() method returns the next value from the iterator.
If there are no more items to return, it should raise StopIteration.

class CountUpToThree:
    def __init__(self):
        self.count = 0

    def __iter__(self):
        return self

    def __next__(self):
        if self.count < 3:
            value = self.count
            self.count += 1
            return value
        else:
            raise StopIteration

counter = CountUpToThree()

for c in counter:
    print(c)

0
1
2

A deep dive into itertools library

At its core, itertools offers a suite of building block functions that allow you to iterate over data in a fast, memory-efficient, and developer-friendly way.
These functions can be categorized into three broad types:

Infinite Iterators: These generate an infinite sequence of values.
Combinatoric Generators: These iterators generate outputs by combining inputs in different ways. They are extremely useful when you want to produce complex combinations or permutations of data.
Iterators Terminating on the Shortest Input Sequence: These, like itertools.zip_longest(), itertools.chain(), itertools.takewhile(), produce values from input sequences and stop when the shortest sequence is exhausted.

All iterators in Python output values sequentially, but itertools' operations may be chained together to construct more complicated iterators that can process big data sets without using a lot of memory.
Additionally, because itertools' operations are written in C, they are faster than comparable Python code written using conventional loops.

Itertools is a useful tool for Python programmers because it makes loops more efficient and the code easier to read.
Itertools gives us a better way to run through lists, texts, dictionaries, files, and even our own custom data structures.

Infinite Iterators

Infinite iterators are a unique feature in the itertools module.
They produce an endless sequence of items, only stopping when we explicitly break the loop.
This can be particularly useful in scenarios where we have a repeating pattern or want to generate a continuous sequence.
However, you must be careful when using these to avoid creating an infinite loop in your program.
Let's look at the three main infinite iterator functions: count(), cycle(), and repeat().

`count(start, step)`

The count() function works similarly to the built-in range() function but, instead of stopping at a certain point, it continues indefinitely.
It takes two arguments: start and step.
start is the number at which the count begins, and step is the increment.

from itertools import count

for idx in count(start=100, step=5):
    print(idx)
    if idx > 110:  # Break the loop to prevent an infinite loop
        break

In this example, we start counting from 100 and increase by 5 each time.
The loop will continue indefinitely unless we stop it.
Here, we stop it when i gets larger than 110.

`cycle(iterable)`

The cycle() function cycles through an iterable indefinitely. This can be useful when you have a repeating pattern.

from itertools import cycle

count = 0
for item in cycle("ABC"):
    print(item)
    count += 1
    if count >= 5:  # Break the loop to prevent infinite loop
        break

A
B
C
A
B

In this example, we're cycling through the string 'ABC'.
Once we reach 'C', it starts over with 'A' again.
We stop the loop after 5 iterations.

More advanced example: Cycle through a list

Suppose we want to cycle through a list indefinitely and print out the current item and the next item.

from itertools import cycle

items = ["A", "B", "C"]
cycled_items = cycle(items) # an iterator that returns elements from the iterable indefinitely

current_item = next(cycled_items)  # to advance through the iterator

for _ in range(5):
    next_item = next(cycled_items)
    print(f"Current item: {current_item}\nNext item: {next_item}\n")
    current_item = next_item

Current item: A
Next item: B

Current item: B
Next item: C

Current item: C
Next item: A

Current item: A
Next item: B

Current item: B
Next item: C

`repeat(object, times)`

The repeat() function simply repeats an object over and over again.
By default, it does this indefinitely, but you can also specify the number of times you want the object to be repeated.

from itertools import repeat

for i in repeat(["A", "B"], times=3):
    print(i)
print("\n")
for i in repeat("AB", times=3):
    print(i)

['A', 'B']
['A', 'B']
['A', 'B']


AB
AB
AB

Here, we're repeating the string 'ABC' three times.
Unlike the previous functions, repeat() can terminate on its own if we provide the times argument.

These functions can be very handy in various scenarios.
They allow us to generate data on the fly without having to pre-generate large lists or sequences, making our code more memory efficient.

Combinatoric Iterators

Combinatoric iterators are used to create different types of iterators that generate all possible combinations, permutations, or Cartesian products (a set of all ordered pairs) of an iterable.
They are powerful tools when we need to consider all possible combinations of elements.
Here we'll focus on three functions: product(), permutations(), and combinations().

`product(iterable, repeat)`

The product() function computes the Cartesian product of the input iterable. This is equivalent to nested for-loops.
The repeat argument specifies the number of repetitions of the iterable.
The result is the Cartesian product of the input iterable with itself, repeated the specified number of times.

from itertools import product

for item in product(["A", "B"], repeat=2):
    print(item)

('A', 'A')
('A', 'B')
('B', 'A')
('B', 'B')

In this example, we're generating the Cartesian product of the string 'AB' with itself. This gives us all possible pairs of 'A' and 'B' in a tuple.

`permutations(iterable, r)`

The permutations() function generates all possible permutations of the input iterable. You can specify the length of the permutations using the 'r' argument. If 'r' is not specified, then 'r' defaults to the length of the iterable.

from itertools import permutations

for item in permutations("ABC", r=2):  # equivalent to permutations(["A", "B", "C"], 2)
    print(item)

('A', 'B')
('A', 'C')
('B', 'A')
('B', 'C')
('C', 'A')
('C', 'B')

Here, we're generating all possible 2-element permutations of the string 'ABC'.
Each permutation is a tuple of two characters.

`combinations(iterable, r)`

The combinations() function generates all possible combinations of the input iterable.
The r argument specifies the length of the combinations. Unlike permutations, combinations don't consider the order of elements.

from itertools import combinations

for item in combinations(["A", "B", "C"], r=2):
    print(item)

('A', 'B')
('A', 'C')
('B', 'C')

Here, we'll generate every pairwise permutation of the items in the list ["A", "B", "C"].

These operations come in handy when trying to solve a problem that requires us to think about every conceivable combination or subset of the given items.

Terminating Iterators

Functions that return a single iterable after using up all elements in the input iterable are called terminating iterators.
They are used to reduce the input iterable in some way.
For this section, we'll focus on accumulate(), groupby(), and chain().

`accumulate(iterable, func)`

The accumulate() function provides a way to get the sum of values or the sum of the outcomes of other binary operations.
In the absence of a specified function, addition will be used.

from itertools import accumulate

list_ = [3, 4, 6, 2, 1, 9, 8]
for item in accumulate(list_, func=max):
    print(item)
# accumulate([3], func=max) -> 3
# accumulate([3, 4], func=max) -> 4
# accumulate([3, 4, 6], func=max) -> 6
# accumulate([3, 4, 6, 2], func=max) -> 6
# accumulate([3, 4, 6, 2, 1], func=max) -> 6
# accumulate([3, 4, 6, 2, 1, 9], func=max) -> 9
# accumulate([3, 4, 6, 2, 1, 9, 8], func=max) -> 9

In this example, we're using accumulate() with the max function to print the maximum value encountered at each step in the list.

`groupby(iterable, key)`

The groupby() function makes an iterator that returns consecutive keys and groups from the iterable. The key is a function that computes a key value for each element.

from itertools import groupby

list_ = [
    ("apple", "fruit"), 
    ("orange", "fruit"), 
    ("lettuce", "vegetable"), 
    ("spinach", "vegetable")
]
for key, group in groupby(list_, key=lambda x: x[1]):
    print(f'"{key}" group: ', list(group))

"fruit" group:  [('apple', 'fruit'), ('orange', 'fruit')]
"vegetable" group:  [('lettuce', 'vegetable'), ('spinach', 'vegetable')]

In this case, we're classifying a set of tuples according to their second element (thus, x[1]), which makes them either fruit or vegetable.

`chain(iterables)`

The chain() function is used to treat multiple sequences as one continuous sequence.

from itertools import chain

list_1 = ["A", "B"]
list_2 = [1, 2, 3]
s = "cd"

for each in chain(list_1, list_2, s):
    print(each)

A
B
1
2
3
c
d

In this example, we're using chain() to treat three separate lists as if they were one long list and iterating over their contents.

Conclusion

In conclusion, the itertools module is a hidden gem in Python that enables simpler, more efficient code to be written when dealing with iterations.
It simplifies our work by providing a set of tools for building and manipulating iterators that can handle complicated iteration patterns.
As we deal with bigger datasets, efficiency in terms of memory use also becomes more crucial.
In this post, we covered three main classes of itertools methods, which are: 1. infinite iterators, 2. combinatoric iterators, and 3. terminating iterators.

Despite its benefits, itertools is still one of Python's lesser-known standard libraries.
itertools is a necessary element of every Python programmer's arsenal because of the variety of powerful capabilities it offers for looping, iterating, and producing combinations or permutations.
Learning itertools is a good investment of time, whether you're an experienced Pythonista wanting to hone your coding skills or a beginner trying to get a feel for Python's potential.

📓 This notebook is accompanying the article https://ealizadeh.com/blog/itertools/.

References

[1] Python Software Foundation, “itertools — Functions creating iterators for efficient looping,” May 23, 2023. https://docs.python.org/3/library/itertools.html

[2] Python Software Foundation, “The Python Standard Library » Built-in Types,” May 25, 2023. https://docs.python.org/3/library/stdtypes.html#iterator-types

Taming Text with string2string: A Powerful Python Library for String-to-String Algorithms

Essi Alizadeh — Fri, 02 Jun 2023 02:44:27 +0000

Introduction

The string2string library is an open-source tool that has a full set of efficient methods for string-to-string problems.
String pairwise alignment, distance measurement, lexical and semantic search, and similarity analysis are all covered in this library.
Additionally, a variety of useful visualization tools and metrics that make it simpler to comprehend and evaluate the findings of these approaches are also included.

The library has well-known algorithms like the Smith-Waterman, Hirschberg, Wagner-Fisher, BARTScore, BERTScore, Knuth-Morris-Pratt, and Faiss search.
It can be used for many jobs and problems in natural-language processing, bioinformatics, and computer social studies [1].

The Stanford NLP group, which is part of the Stanford AI Lab, has developed the library and introduced it in [1].
The library's GitHub repository has several tutorials that you may find useful.

A string is a sequence of characters (letters, numbers, and symbols) that stands for a piece of data or text.
From everyday phrases to DNA sequences, and even computer programs, strings may be used to represent just about everything [1].

Installation

You can install the library via pip by running pip install string2string.

Pairwise Alignment

String pairwise alignment is a method used in NLP and other disciplines to compare two strings, or sequences of characters, by highlighting their shared and unique characteristics.
The two strings are aligned, and a similarity score is calculated based on the number of shared characters, as well as the number of shared gaps and mismatches.
This procedure is useful for locating sequences of characters that share similarities and calculating the "distance" between two sets of strings.
Spell checking, text analysis, and bioinformatics sequence comparison (e.g., DNA sequence alignment) are just some of the many uses for it.

Currently, the string2string package provides the following alignment techniques:

Needleman-Wunsch for global alignment
Smith-Waterman for local alignment
Hirchberg's algorithm for linear space global alignment
Longest common subsequence
Longest common substring
Dynamic time warping (DTW) for time series alignment

In this post, we'll look at two examples: one for global alignment and one for time series alignment.

Needleman-Wunsch Algorithm for Global Alignment

The Needleman-Wunsch algorithm is a type of dynamic programming algorithm that is often used in bioinformatics to match two DNA or protein sequences, globally.

from string2string.alignment import NeedlemanWunsch

nw = NeedlemanWunsch()

# Define two sequences
s1 = 'ACGTGGA'
s2 = 'AGCTCGC'

aligned_s1, aligned_s2, score_matrix = nw.get_alignment(s1, s2, return_score_matrix=True)

print(f'The alignment between "{s1}" and "{s2}":')
nw.print_alignment(aligned_s1, aligned_s2)

The alignment between "ACGTGGA" and "AGCTCGC":
A | C | G | - | T | G | G | A
A | - | G | C | T | C | G | C

For a more informative comparison, we can use plot_pairwise_alignment() function in the library.

from string2string.misc.plotting_functions import plot_pairwise_alignment

path, s1_pieces, s2_pieces = nw.get_alignment_strings_and_indices(aligned_s1, aligned_s2)

plot_pairwise_alignment(
    seq1_pieces=s1_pieces,
    seq2_pieces=s2_pieces,
    alignment=path,
    str2colordict={
        "A": "pink", 
        "G": "lightblue", 
        "C": "lightgreen", 
        "T": "yellow", 
        "-": "lightgray"
    },
    title="",
    seq1_name="Sequence 1",
    seq2_name="Sequence 2",
)

Dynamic Time Warping

DTW is a useful tool to compare two time series that might differ in speed, duration, or both.
It discovers the path across these distances that minimizes the total difference between the sequences by calculating the "distance" between each pair of points in the two sequences.

Let's go over an example using the alignment module in the string2string library.

from string2string.alignment import DTW

dtw = DTW()

x = [3, 1, 2, 2, 1]
y = [2, 0, 0, 3, 3, 1, 0]

dtw_path = dtw.get_alignment_path(x, y, distance="square_difference")
print(f"DTW path: {dtw_path}")

DTW path: [(0, 0), (1, 1), (1, 2), (2, 3), (3, 4), (4, 5), (4, 6)]

Above is an example borrowed from my previous post, An Illustrative Introduction to Dynamic Time Warping.
For those looking to delve deeper into the topic, in [2], I explained the core concepts of DTW in a visual and accessible way.

Search Problems

String search is the task of finding a pattern substring within another string.
The library offers two types of search algorithms: lexical search and semantic search.

Lexical Search (exact-match search)

Lexical search, in layman's terms, is the act of searching for certain words or phrases inside a text, analogous to searching for a word or phrase in a dictionary or a book.

Instead of trying to figure out what a string of letters or words means, it just tries to match them exactly.
When it comes to search engines and information retrieval, lexical search is a basic strategy to finding relevant resources based on the keywords or phrases users enter, without any attempt at comprehending the linguistic context of the words or phrases in question.

Currently, the string2string library provides the following lexical search algorithm:

Naive (brute-force) search algorithm
Rabin-Karp search algorithm
Knuth-Morris-Pratt (KMP) search algorithm (see the example below)
Boyer-Moore search algorithm

from string2string.search import KMPSearch

kmp_search = KMPSearch()

pattern = "Redwood tree"
text = "The gentle fluttering of a Monarch butterfly, the towering majesty of a Redwood tree, and the crashing of ocean waves are all wonders of nature."

idx = kmp_search.search(pattern=pattern, text=text)

print(f"The starting index of pattern: {idx}")
print(f'The pattern (± characters) inside the text: "{text[idx-5: idx+len(pattern)+5]}"')

The starting index of pattern: 72
The pattern (± characters) inside the text: "of a Redwood tree, and"

Semantic Search

Semantic search is a more sophisticated method of information retrieval that goes beyond simple word or phrase searches.
It employs NLP (natural language processing) to decipher a user's intent and return accurate results.

To put it another way, let's say you're interested in "how to grow apples."
While a lexical search may produce results including the terms "grow" and "apples," a semantic search will recognize that you are interested in the cultivation of apple trees and deliver results accordingly.
The search engine would then prioritize results that not only included the phrases it was looking for but also gave relevant information about planting, trimming, and harvesting apple trees.

Semantic Search via Faiss

Faiss (Facebook AI Similarity Search) is an efficient similarity search tool that is useful for dealing with high-dimensional data with numerical representations [3].
The string2string library has a wrapper for the FAISS library developed by Facebook (see GitHub repository.

In short, Faiss search ranks its results based on a "score," representing the degree to which two objects are similar to one another.
The score makes it possible to interpret and prioritize search results based on how close/relevant they are to the desired target.

Let's see how the Faiss search is used in the string2string library.
Here, we have a corpus^[A corpus (plural of corpora) is a large and structured collections of texts used for linguistic research, NLP and ML applications.] of 11 sentences, and we will do a semantic search by querying a target sentence to see how close/relevant it is to these sentences.

corpus = {"text": [
    "A warm cup of tea in the morning helps me start the day right.",
    "Staying active is important for maintaining a healthy lifestyle.",
    "I find inspiration in trying out new activities or hobbies.",
    "The view from my window is always a source of inspiration.",
    "The encouragement from my loved ones keeps me going.",
    "The novel I've picked up recently has been a page-turner.",
    "Listening to podcasts helps me stay focused during work.",
    "I can't wait to explore the new art gallery downtown.",
    "Meditating in a peaceful environment brings clarity to my thoughts.",
    "I believe empathy is a crucial quality to possess.",
    "I like to exercise a few times a week."
    ]
}

query = "I enjoy walking early morning before I start my work."

Let's initialize the FaissSearch object. Facebook's BART Large model is the default model and tokenizer for the FaissSearch object.

from string2string.search import FaissSearch

faiss_search = FaissSearch(
    model_name_or_path = "facebook/bart-large",
    tokenizer_name_or_path = "facebook/bart-large",
)

faiss_search.initialize_corpus(
    corpus=corpus,
    section="text", 
    embedding_type="mean_pooling",
)

Let's find the top 3 most similar sentences in the corpus to the query and print them, as well as their similarity scores.

top_k_similar_answers = 3
most_similar_results = faiss_search.search(
    query=query,
    k=top_k_similar_answers,
)

print(f"Query: {query}\n")
for i in range(top_k_similar_answers):
    print(f'Result {i+1} (score={most_similar_results["score"][i]:.2f}): "{most_similar_results["text"][i]}"')

Query: I enjoy walking early morning before I start my work.

Result 1 (score=208.49): "I find inspiration in trying out new activities or hobbies."
Result 2 (score=218.21): "I like to exercise a few times a week."
Result 3 (score=225.96): "I can't wait to explore the new art gallery downtown."

Distance

String distance is the task of quantifying the degree to which two supplied strings differ using a distance function.
Currently, the string2string library offers the following distance functions:

Levenshtein edit distance
Damerau-Levenshtein edit distance
Hamming distance
Jaccard distance^[Not to be confused with Jaccard similarity coefficient. Jaccard distance = 1 - Jaccard coefficient]

Levenshtein edit distance

Levenshtein edit distance, or simply the edit distance, is the minimal number of insertions, deletions, or substitutions needed to convert one string into another.

from string2string.distance import LevenshteinEditDistance

edit_dist = LevenshteinEditDistance()

# Create two strings
s1 = "The beautiful cherry blossoms bloom in the spring time."
s2 = "The beutiful cherry blosoms bloom in the spring time."

# Let's compute the edit distance between the two strings and measure the computation time
edit_dist_score  = edit_dist.compute(s1, s2, method="dynamic-programming")

print(f'The distance between the following two sentences is {edit_dist_score}:') #\n- "{s1}"\n- "{s2}"')
print(f'"The beautiful cherry blossoms bloom in the spring time."')
print(f'"The beutiful cherry blosoms bloom in the spring time."')

The distance between the following two sentences is 2.0:
"The beautiful cherry blossoms bloom in the spring time."
"The beutiful cherry blosoms bloom in the spring time."

Jaccard Index

The Jaccard index can be used to quantify the similarity between sets of words or tokens and is commonly used in tasks such as document similarity or topic modeling.
For example, the Jaccard index can be used to measure the overlap between the sets of words in two different documents or to identify the most similar topics across a collection of documents.

from string2string.distance import JaccardIndex 

jaccard_dist = JaccardIndex()

# Suppose we have two documents
doc1 = ["red", "green", "blue", "yellow", "purple", "pink"]
doc2 = ["green", "orange", "cyan", "red"]

jaccard_dist_score = jaccard_dist.compute(doc1, doc2)

print(f"Jaccard distance between doc1 and doc2: {jaccard_dist_score:.2f}")

Jaccard distance between doc1 and doc2: 0.75

Similarity

To put it simply, string similarity determines the degree to which two strings of text (or sequences of characters) are linked or similar to one another.
Take, as an example, the following pair of sentences:

"The cat sat on the mat."
"The cat was sitting on the rug."

Although not identical, these statements share vocabulary and convey a connected sense.
Methods based on string similarity analysis reveal and quantify the degree of similarity between such text pairings.

There is a duality between string similarity and distance measures, meaning that they can be used interchangeably [1].

The similarly module of the string2string library currently offers the following algorithms:

Cosine similarity
BERTScore
BARTScore
Jaro similarity
LCSubsequence similarity

Let's go over an example of the BERTScore similarity algorithm with the following four sentences:

The bakery sells a variety of delicious pastries and bread.
The park features a playground, walking trails, and picnic areas.
The festival showcases independent movies from around the world.
A range of tasty bread and pastries are available at the bakery.

Sentences 1 and 2 are similar semantically, as both are about bakery and pastry.
Hence, we should expect a high similarity score between the two.

Let's implement the above example in the library.

from string2string.similarity import BERTScore
from string2string.misc import ModelEmbeddings

bert_score = BERTScore(model_name_or_path="bert-base-uncased")
bart_model = ModelEmbeddings(model_name_or_path="facebook/bart-large")

sentences = [
    "The bakery sells a variety of delicious pastries and bread.", 
    "The park features a playground, walking trails, and picnic areas.", 
    "The festival showcases independent movies from around the world.", 
    "A range of tasty bread and pastries are available at the bakery.", 
]

embeds = [
    bart_model.get_embeddings(
        sentence, embedding_type='mean_pooling'
    ) for sentence in sentences
]

# Define source and target sentences (to compute BERTScore for each pair)
source_sentences, target_sentences = [], []
for i in range(len(sentences)):
    for j in range(len(sentences)):
        source_sentences.append(sentences[i])
        target_sentences.append(sentences[j])

# You can rewrite above in a more concise way using itertools.product
# from itertools import product
# source_sentences, target_sentences = map(
#   list, zip(*product(sentences, repeat=2))
# )

bertscore_similarity_scores = bert_score.compute(
    source_sentences,
    target_sentences,
)
bertscore_precision_scores = bertscore_similarity_scores['precision'].reshape(
    len(sentences), len(sentences)
)

We can visualize the similarity between every pair of sentences using the plot_heatmap() function provided in the library.

from string2string.misc.plotting_functions import plot_heatmap

plot_ticks = [f"Sentence {i + 1}" for i in range(len(sentences))]

# We can also visualize the BERTScore similarity scores using a heatmap
plot_heatmap(
    bertscore_precision_scores,
    title="",
    x_ticks=plot_ticks,
    y_ticks=plot_ticks,
    x_label="",
    y_label="",
    valfmt="{x:.2f}",
    cmap="Blues",
)

As can be seen above, sentences 1 and 4 are much more similar (using the BERTScore algorithm) as we expected.

📓 You can find the Jupyter notebook for this blog post on GitHub.

Conclusion

The string2string Python library is an open-source tool that provides a full set of efficient methods for string-to-string problems.
In particular, the library has four main modules that address the following tasks: 1. pairwise alignment including both global and local alignments; 2. distance measurement; 3. lexical and semantic search; and 4. similarity analysis.
The library offers various algorithms in each category and provides helpful visualization tools.

References

[1] M. Suzgun, S. M. Shieber, and D. Jurafsky, “string2string: A modern python library for string-to-string algorithms,” 2023, Available: http://arxiv.org/abs/2304.14395

[2] E. Alizadeh, “An Illustrative Introduction to Dynamic Time Warping,” 2020. https://ealizadeh.com/blog/introduction-to-dynamic-time-warping/

[3] J. Johnson, M. Douze, and H. Jégou, “Billion-scale similarity search with GPUs,” IEEE Transactions on Big Data, vol. 7, no. 3, pp. 535–547, 2019.