Algorithm Chapter 5 String Notes, Polytechnic 3rd sem Algorithm notes

5. Strings

In computer science, strings are sequences of characters used to represent text. A string can include letters, digits, punctuation, and special characters. Strings are a fundamental data type in programming languages and play a key role in various algorithms and data structures. Below are detailed explanations of specific string-related topics.

5.1. String Sort

String Sorting is the process of arranging strings in a particular order, typically lexicographical (dictionary order). String sorting is important for search algorithms, organizing data, and making comparisons.

Types of String Sorting Algorithms:

1. Lexicographic Order: This is the most common string sorting method. Strings are compared character by character, and the comparison is based on their ASCII (or Unicode) values.

   • Example: "apple" comes before "banana" because 'a' comes before 'b'.

2. Radix Sort for Strings: Radix sort is a non-comparative sorting algorithm that works by distributing strings into buckets according to their individual characters, processing the characters from the least significant to the most significant.

   • Radix sort can handle fixed-length strings efficiently and is used in applications like sorting zip codes or other fixed-length data.

3. Merge Sort and Quick Sort for Strings: These comparison-based sorting algorithms can also be applied to strings by comparing characters. While efficient for general sorting, they may not be as optimized as specialized string-sorting techniques like radix sort.

4. Bucket Sort: This technique is effective for sorting strings of known, fixed length. It organizes the strings into buckets based on their initial characters, and then each bucket is sorted individually.

Applications of String Sorting:

• Alphabetizing a list of names.
• Sorting words in a dictionary or database.
• Preparing data for binary search algorithms.

5.2. Tries

Tries, also known as prefix trees, are tree-based data structures that store strings in a way that allows for efficient searching, insertion, and deletion operations.

Structure of a Trie:

• A trie is composed of nodes where each node represents a single character in the string.
• Strings are stored from the root to the leaves of the tree, and common prefixes are shared among strings.
• Each path from the root to a leaf corresponds to a string.

Operations on Tries:

1. Insert: Adding a string to a trie involves traversing through the nodes that correspond to the characters of the string, creating new nodes as needed.
2. Search: Searching for a string involves checking if the characters of the string exist in the trie from the root to the leaf. If all characters exist, the string is present.
3. Delete: Deleting a string from a trie involves removing nodes if they no longer represent a valid string and do not affect other strings.

Applications of Tries:

• Autocomplete systems: Tries are used to quickly suggest completions for a given prefix.
• Spell checkers: Tries store dictionaries of words to efficiently check whether a word exists.
• IP routing: Tries are used in network routing to quickly determine the next hop based on IP address prefixes.

5.3. Substring Search

Substring Search is the problem of finding if a substring exists within a larger string, and if so, determining its position.

Common Substring Search Algorithms:

1. Brute Force: The brute force method compares the substring with every possible substring of the main string. While simple, this method can be inefficient, with a time complexity of O(nm) (where n is the length of the string and m is the length of the substring).

2. Knuth-Morris-Pratt (KMP) Algorithm: The KMP algorithm improves substring search by preprocessing the pattern to identify where partial matches occur, thus avoiding redundant comparisons.

   • Time complexity: O(n + m).

3. Rabin-Karp Algorithm: This algorithm uses hashing to find the substring. It calculates a hash for the substring and for every possible substring in the main string of the same length. If the hashes match, the strings are compared to confirm the match.

   • Time complexity: O(n + m) in the average case.

4. Boyer-Moore Algorithm: This algorithm compares the pattern from right to left and skips over sections of the text that are guaranteed not to match, making it very efficient in practice.

   • Time complexity: O(n) in the best case.

Applications of Substring Search:

• Text editors for finding words or phrases in a document.
• DNA sequence matching in bioinformatics.
• Search engines for keyword matching.

5.4. Regular Expressions

Regular Expressions (Regex) are sequences of characters that define a search pattern. They are powerful tools used for pattern matching and string manipulation in text.

Components of Regular Expressions:

• Literal Characters: Characters like a, b, or 1 are matched as-is.
• Metacharacters: Special characters that have a specific meaning in regex, such as:
  • .: Matches any single character.
  • *: Matches zero or more occurrences of the previous character.
  • +: Matches one or more occurrences of the previous character.
  • []: Specifies a character set. [abc] matches any of the characters 'a', 'b', or 'c'.
  • ^ and $: Used to match the beginning and end of a string respectively.

Operations Using Regular Expressions:

1. Search: Find patterns in text, like finding email addresses in a document.
2. Replace: Replace matched patterns with new strings.
3. Split: Split a string based on a regex pattern, such as splitting a sentence into words.

Applications of Regular Expressions:

• Validating user input, such as checking if an email address or phone number is correctly formatted.
• Extracting data from web pages or text files.
• Text manipulation in programming, such as cleaning and preprocessing data.

5.5. Elementary Data Compression

Elementary Data Compression involves reducing the size of data to save storage space or transmission time.

Types of Data Compression:

1. Lossless Compression: This type of compression allows the original data to be perfectly reconstructed from the compressed data. Common lossless techniques include:
   • Huffman Coding: An entropy-based compression method where frequently occurring characters are assigned shorter codes, and less frequent characters are assigned longer codes.
   • Run-Length Encoding (RLE): Encodes consecutive repeated characters or data elements with a single character and a count. For example, "AAAAA" would be encoded as "A5".
   • Lempel-Ziv-Welch (LZW): A dictionary-based algorithm that replaces repeating patterns of data with references to a dictionary.
2. Lossy Compression: This type of compression sacrifices some data accuracy to achieve higher compression ratios, typically used in multimedia (e.g., JPEG for images, MP3 for audio).

Applications of Data Compression:

• File storage: Compressing files to save space on disk.
• Transmission: Reducing the size of data being transmitted over networks.
• Multimedia: Reducing the size of images, audio, and video files without noticeable quality loss (in the case of lossy compression).

---

These topics are fundamental to string manipulation, pattern matching, and data processing in computer science. The understanding and application of these concepts are critical for efficient algorithm design, especially in fields like text processing, network communication, and data compression