itu.algs4.strings package

Submodules

itu.algs4.strings.boyer_moore module

class itu.algs4.strings.boyer_moore.BoyerMoore(pat)

Bases: object

The BoyerMoore class finds the first occurence of a pattern string in a text string.

This implementation uses the Boyer-Moore algorithm (with the bad- character rule, but not the strong good suffix rule).

search(txt)

Returns the index of the first occurrrence of the pattern string in the text string.

Parameters:txt – the text string
Returns:the index of the first occurrence of the pattern string

in the text string; N if no such match

itu.algs4.strings.boyer_moore.main()

Takes a pattern string and an input string as command-line arguments; searches for the pattern string in the text string; and prints the first occurrence of the pattern string in the text string.

Will print the pattern after the end of the string if no match is found.

itu.algs4.strings.huffman_compression module

The Huffman compression module provides static methods for compressing and expanding a binary input using Huffman codes over the 8-bit extended ASCII alphabet.

For additional documentation, see Section 5.5 of Algorithms, 4th edtition by Robert Sedgewick and Kevin Wayne.

itu.algs4.strings.huffman_compression.compress()

Reads a sequence of 8-bit bytes from standard input; compresses them using Huffman codes with an 8-bit alphabet; and writes the results to standard input.

itu.algs4.strings.huffman_compression.expand()

Reads a sequence of bits that represents a Huffman-compressed message from standard input; expands them; and writes the results to standard output.

itu.algs4.strings.huffman_compression.main()

Sample client that calss compress() if the command-line argument is “-“, and expand() if it is “+”.

itu.algs4.strings.kmp module

The KMP (Knuth-Morris-Pratt) class finds the first occurrence of a pattern string in a text string. This implementation uses a version of the Knuth-Morris-Pratt substring search algorithm. The version takes time as space proportional to N + M R in the worst case, where N is the length of the text string, M is the length of the pattern, and R is the alphabet size.

class itu.algs4.strings.kmp.KMP(pat)

Bases: object

search(txt)

Returns the index of the first occurrrence of the pattern string in the text string.

Parameters:txt – the text string
Returns:the index of the first occurrence of the pattern string

in the text string; N if no such match

itu.algs4.strings.kmp.main()

Takes a pattern string and an input string as command-line arguments; searches for the pattern string in the text string; and prints the first occurrence of the pattern string in the text string.

Will print the pattern after the end of the string if no match is found.

itu.algs4.strings.lsd module

This module provides functions for sorting arrays of strings using lsd sort.

For additional documentation, see Section 5.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

itu.algs4.strings.lsd.sort(a, w, radix=256)

Rearranges the array of w-character strings in ascending order.

Parameters:
  • a – the array to be sorted
  • w – the number of characters per string
  • radix – an optional number specifying the size of the alphabet to sort

itu.algs4.strings.lzw module

The LSW module provides static methods for compressing and expanding a binary input using LZW over the 8-bit extended ASCII alphabet with 12-bit codewords.

For additional documentation see Section 5.5 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

itu.algs4.strings.lzw.compress()

Reads a sequence of 8-bit bytes from standard input; compresses them using LZW compression with 12-bit codewords; and writes the results to standard output.

itu.algs4.strings.lzw.expand()

Reads a sequence of bit encoded using LZW compression with 12-bit codewords from standard input; expands them; and writes the results to standard output.

itu.algs4.strings.lzw.main()

Sample client that calls compress() if the command-line argument is “-“, and expand() if it is “+”.

Example: echo huhu | python3 algs4/strings/lzw.py - | python3 algs4/strings/lzw.py +

itu.algs4.strings.msd module

This module provides functions for sorting arrays of strings using msd sort.

For additional documentation, see Section 5.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

itu.algs4.strings.msd.sort(a, radix=256)

Rearranges the array of 32-bit integers in ascending order. Currently assumes that the integers are nonnegative.

Parameters:a – the array to be sorted

itu.algs4.strings.nfa module

class itu.algs4.strings.nfa.NFA(regex)

Bases: object

The NFA class provides a data type for creating a nondeterministic finite state automaton (NFA) from a regular expression and testing whether a given string is matched by that regular expression. It supports the following operations: concatenation, closure, binary or, and parentheses, metacharacters (either in the text or pattern), capturing capabilities, greedy or reluctant/lazy modifiers, and other features in industrial-strength implementations such as Java’s Pattern and Matcher.

This implementation builds the NFA using a digraph and a stack and simulates the NFA using digraph search (see the textbook for details). The constructor takes time proportional to m, where m is the number of characters in the regular expression. The recognizes() method takes time proportional to m*n, where n is the number of characters in the text.

For additional documentation, see section 5.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

recognizes(txt)

Returns True if the text is matched by the regular expression.

Parameters:txt – the text
Returns:True if the text is matched by the regular expression; False otherwise
itu.algs4.strings.nfa.main()

Unit tests the NFA data type.

itu.algs4.strings.quick3string module

The Quick3String module provides functions for sorting an array of strings using 3-way radix quicksort.

itu.algs4.strings.quick3string.is_sorted(a)

Returns true if a is sorted.

Parameters:a – the array to be checked.
Returns:True if a is sorted.
itu.algs4.strings.quick3string.main()

Reads in a sequence of fixed-length strings from standard input; 3-way radix quicksorts them; and prints them to standard output in ascending order.

itu.algs4.strings.quick3string.sort(a)

Rearranges the array of strings in ascending order.

Parameters:a – the array to be sorted.

itu.algs4.strings.rabin_karp module

class itu.algs4.strings.rabin_karp.RabinKarp(pat)

Bases: object

The RabinKarp class finds the first occurence of a pattern string in a text string.

This implementation uses the Monte Carlo version of the Rabin-Karp algorithm.

search(txt)

Returns the index of the first occurrrence of the pattern string in the text string.

Parameters:txt – the text string
Returns:the index of the first occurrence of the pattern string

in the text string; N if no such match

itu.algs4.strings.rabin_karp.long_random_prime(k)

Generates a random prime.

Parameters:k – the desired bit length of the prime
Returns:a random prime of bit length k
itu.algs4.strings.rabin_karp.main()

Takes a pattern string and an input string as command-line arguments; searches for the pattern string in the text string; and prints the first occurrence of the pattern string in the text string.

Will print the pattern after the end of the string if no match is found.

itu.algs4.strings.trie_st module

class itu.algs4.strings.trie_st.TrieST

Bases: object

class Node

Bases: object

R = 256
R = 256
contains(key)
delete(key)
get(key)
is_empty()
keys()
keys_that_match(pattern)
keys_with_prefix(prefix)
longest_prefix_of(query)
put(key, val)
size()
itu.algs4.strings.trie_st.test()

itu.algs4.strings.tst module

class itu.algs4.strings.tst.TST

Bases: object

class Node

Bases: object

contains(key)
get(key)
keys()
keys_that_match(pattern)
keys_with_prefix(prefix)
longest_prefix_of(query)
put(key, val)
size()
itu.algs4.strings.tst.test()

Module contents