3.

4
Text Processing and Pattern Matching

Department of CSE,Coimbatore
Objectives
• To explore how computers can be used to create, process, and
reason about textual information.
• To understand strings and string operations.
• To learn to process textual information.
• To learn to recognize patterns.
• To understand that string literals can be rewritten as patterns.

Department of CSE,Coimbatore
Strings
 Although much of the information stored on computers involves numbers, the majority of
data is textual rather than numeric.
• For example, your name, social security number, address, and Facebook status
are all textual in nature.
• Computer programmers use the term string when referring to textual data.
• A string is simply a piece of text, or more formally, an ordered sequence of
individual characters.
 You can think of a single character as the result of any one key that you press on a
keyboard.
• A character is usually a
• letter of the alphabet, but a character might also be a punctuation symbol
such as a comma, semicolon, or question mark.
• even be a nonprintable character such as a tab or a linefeed.
Department of CSE,Coimbatore
String Length
• The length of a string is the number of characters contained in
the string.

• The length of a string may be zero, if the string contains no

characters, and it may be larger than zero.

• No string has a negative length since it is not possible to have a

sequence that contains a negative number of characters.
Department of CSE,Coimbatore
String Literal
• In most programming languages, string data is denoted by using double
quotes to surround the text.
• For example, “Hello” is a string having five characters.
• Any sequence of characters that is enclosed by double-quotes is known
as a string literal.
The double quotes are not part of the string itself.
They simply serve to notify the computer that the enclosed text is a string literal.
• Since digits appear on the keyboard, strings may contain digits in addition
to alphabetic characters.
• Consider, for example the string literal “04/13/65”.
• This string has a length of 8 where the characters at indices 2 and 5 are
both forward slashes (/), but the remaining characters are digits.

Department of CSE,Coimbatore
String Indices
• The characters in a string are indexed such that the first character
has an index of 0, the second character has an index of 1, and so on.
• In the Figure: Indexing in the string “Hello” , each character of the
string “Hello” is given an index.
• The top row shows the indices of each character, while the
characters themselves occur in the second row.
• We note that the character at index 0 is H, the character at index 1 is
e, and the character at index 4 is o.
0 1 2 3 4 Indices
H e l l o
Figure: Indices in the string “Hello”

Department of CSE,Coimbatore
Observe
• The length of the string “Hello” is 5, while the largest index is 4.

• This observation suggests that for any string of length n, the largest
valid index is n–1.

• Since the smallest possible index is always 0, we note that for any
string of length n, the only valid indices are in the interval 0 to n–1.

Department of CSE,Coimbatore
Indexing operation
• Given a string literal we can access the character at a particular index by using
a bracket notation.
• The expression stringliteral[index of character] produces a string containing
one letter.
• This is referred to as an indexing operation.
0 1 2 3 4 5 6
p o p c o r n Figure: Indices in the string “popcorn”
• Eg. Access the fourth letter of the string literal “popcorn”.
• The fourth character has an index of 3.
• We write the number 3 inside of the brackets following the string
literal as “popcorn” [3].
• This expression produces a string containing a lowercase c.
• Eg. “popcorn” [15] is an invalid indexing.
• The indices are in the interval 0 to 6.
• The expression produces an error.
Department of CSE,Coimbatore
Length operation
• The expression [Link] produces the length of the
string.
• Eg. “popcorn”.length produces the number 7 (the length of the string).
• Note that the expression “popcorn”.length is interchangeable with the
value produced by the expression (the number 7).

Length is 9

Length is 5
Department of CSE,Coimbatore
Concatenation operation
• String concatenation is another common string processing operation.
• It takes two strings and splices them to form a third string as output.
• String concatenation is usually expressed, as a plus symbol (+).
• Although we usually think of the plus symbol as referring to the
mathematical addition of two numbers, the plus symbol is also
employed to concatenate two strings.
• Eg. the expression “mother” + “land” concatenates the two strings
“mother” and “land” can be concatenated to produce the string
“motherland”.

Department of CSE,Coimbatore
String variables
• Recall that variables are bound to data through a name binding operation that
we denote using the left-arrow symbol (←).
• On the left of this symbol must be a variable name and a value must occur on
the right of the arrow. x ← “pop”
y ← “corn”
z←x+y
Figure: String variables
• Figure: String variables shows how we might use string variables to refer to
string literals.
• In this sequence of actions we tell the computer to
(1) bind the name x to the string literal “pop”
(2) bind the name y to the string literal “corn”
(3) bind the name z to the string “popcorn”
• z is produced by concatenating the strings referred to by the variables x and y.
Department of CSE,Coimbatore
Substring operation
• Although indexing allows us to obtain an individual character of a
string, we often want to obtain a subsequence of a string.
• The expression [Link](a,b) produces the sequence of
characters spanning indices a to b-1 of the string variable.
• The substring function allows us to obtain part of a string if we know
the indices of the first and last characters that we want to extract from
the string.
• An example of the substring function is shown in Figure: Extracting
subsequence of a string.
x ← “computational thinking”
y ← [Link](3, 6)
Figure: Extracting subsequence of a string
Department of CSE,Coimbatore
Substring contd---
• The function substring is applied to the x variable, which is
bound to the string “computational thinking”.
• Why use index 6 ?
• It denotes the index of the first character that is not included in the
output i.e.(3,6].
• We are telling the computer to give us the sequence of
characters starting from the character at index 3 and ending
with the character at index 5 of the variable x.
• The variable y is bound to the string “put”.

Department of CSE,Coimbatore
IndexOf operation- Handy for searching!

• Sometimes it is useful to find the index of some character in a string literal.

• The expression [Link](character) searches a string literal for a
character and returns the index of the first occurrence of the character.
• Consider, for example, the e-mail address
“elvispresley@[Link]”.
• We might want to know where the character ‘@’ occurs in the string so
that we can split the string into two parts: the user name and the name of
the e-mail service.
• x ← “elvispresley@[Link]”. indexOf(“@”)

Department of CSE,Coimbatore
IndexOf operation contd---
x ← “popcorn”.indexOf(“c”)
Figure: Obtain index of first occurrence of “c”
• The value produced by this expression is the number 3, since that
first lowercase c occurs at index 3 in the string literal “popcorn”.

• Note that , “popcorn”.indexOf(“c”) is interchangeable with the

number 3(the data that the expression produces).

• An invalid index produces the number –1.

Department of CSE,Coimbatore
Eg. Processing e-Mail Addresses
• We will consider how e-mail addresses, a very common piece of textual
data, can be automatically processed and analyzed for use in a business
setting.
• Perhaps we are creating a company to sell T-shirts to college students.
• We establish a policy that requires users to register prior to browsing our
catalog and ordering products.
• We require that each user provide an e-mail address and a password.
• We know that an e-mail (Figure: e-Mail addresses) consists of two general
parts: a user name (also referred to as the local part) and a host site (also
referred to as the domain part). These two parts are separated by the ampersat
(@) symbol.
Figure: e-Mail addresses

Department of CSE,Coimbatore
Eg. Processing e-Mail Addresses contd---
• To verify that the user is a college student, we establish a policy requiring
that the provided e-mail address terminate with the characters edu.
• This part of an e-mail address is referred to as the domain extension.
• By convention, any e-mail address having edu as the domain extensions is
understood to be an educational institution.
• In addition we would also like to separate the user name from the e-mail
host site so that we can track the number of users associated with each
educational institution.
• We realize that our web registration system must accept any e-mail address
typed in by the user and then extract three vital subsequences:
• the user name, the host site, and the domain extension.

Department of CSE,Coimbatore
Eg. Processing e-Mail Addresses contd---
• As an example, consider the e-mail address
[Link]@[Link].
• This e-mail address has a length of 28 and consists of the user name
[Link], the host site is [Link], and the final three
characters of the host site are edu.
• For this specific e-mail address, we can use the text-processing
commands shown in Figure: Extract the three relevant strings.
address ← readAddressFromUser()
username ← [Link](0, 9)
hostsite ← [Link](10,28)
extension ← [Link](25,28)
Figure: Extract the three relevant strings
Department of CSE,Coimbatore
Eg. Processing e-Mail Addresses contd---
• Note that the command to readAddressFromUser is simply a way of
expressing that the registration web page has a text-entry field from which
we obtain the text entered by the user.
• Since the ampersat occurs at index 9, we know that the username consists
of the first 9 characters of the address and hence we use the substring
statement to extract the corresponding character sequence.
• Also, since the ampersat is at index 9, we can extract the host site by
taking the characters starting at index 10 and moving up until the end of
the string.
• The final three characters are those characters whose indices are given as
28 – 3, 28 – 2, and 28 – 1 where 28 is the length of the address.

Department of CSE,Coimbatore
Generalizing for any e-mail address
• Although this extracts the username, host site, and extension from
the e-mail [Link]@[Link], it will not work for
most other e-mail addresses, say, [Link]@[Link].
• We find that the username is [Link], the host site is
ley@[Link], and the extension is hot.
• Although we might believe that the phrase hot would make a great
domain extension, there is no domain extension for hot websites.
• Observe that we have made two assumptions that are not generally
true of all e-mails:
(1) the ampersat occurs at index 9.
(2) the length of the e-mail address is 28.

Department of CSE,Coimbatore
Generalizing for any e-mail address contd---
• The first assumption is encoded in the phrase “[Link](0,
9)”.
• since we used the number 9 as a result of assuming that the index
of the ampersat is 9.
• The first assumption is encoded in the phrase
“[Link](10,28)”.
• since we understood the number 10 to be the index of the first
character following the ampersat.
• The second assumption is encoded in the phrase
“[Link](10,28)” .
• since we understand the 28 to be the length of the address.

Department of CSE,Coimbatore
Generalizing for any e-mail address contd---
• We can remove these assumptions by first finding the index of the first occurrence of
the ampersat in any address and then finding the length of the address.
• We can then make use of the values to extract the username, host site, and extension
from any e-mail address the user chooses to type.
• The modification are given in Figure: Extracting information from an e-
mail address.

address ← readAddressFromUser()
ampersatIndex ← [Link](“@”)
length ← [Link]
username ← [Link](0, ampersatIndex)
hostsite ← [Link](ampersatIndex+1, 28)
extension ← [Link](length-3, length)
Figure: Extracting information from an e-mail address
Department of CSE,Coimbatore
Processing dates
• The European date format is essentially the reverse of the American date
format.
• Most Americans write a date by putting the month before the day while
Europeans put the day ahead of the month.
• The date April 13, 1965, would be written as 04/13/1965 by an American
and as 13/04/1965 by a European.
• Consider writing a website that requires users to enter a date.
• Perhaps we require the user to enter their birthdate or the date that their
driver’s license was granted.
• We might want to allow a European to enter a date using the European
format but then convert the date to an American format so that it can be
stored in our server’s database using the same format as American users.
We can use text-processing operations to perform this conversion.
Can you try it?
Department of CSE,Coimbatore
Patterns
• Patterns are a very useful technique for processing textual data.
• A pattern defines a set of properties that some strings will possess
and other strings will not.
• In other words, a pattern is a way of determining whether a
particular string is a member of the family defined by the pattern or
whether a particular string is not a member of the family.

Figure: Textual patterns

Department of CSE,Coimbatore
Recognizing patterns
• In the Social Security Number “123-45-6789”, the observed pattern is:
• First 3 digits followed by a dash (-)
• followed by any 2 digits
• followed by a dash
• followed by any 4 digits
• A string literal that matches this pattern can be reasonably understood as a
member of the Social Security number family, whereas a string literal that
does not match this pattern is not a Social Security number.
• A regular expression defines a pattern such that a particular string will either
match the pattern or will not match the pattern.
• Regular expressions are extremely powerful techniques for processing
textual data.

Department of CSE,Coimbatore
Writing patterns
• Consider writing a pattern for the hugs and kisses string as
described in Figure: Basic rules for writing patterns.

Figure: Basic rules for writing patterns

Department of CSE,Coimbatore
Writing patterns contd---
Identify the rules that can be applied for the pattern “XOXO”.
• First we note that according to rule 1, the single character X is a
pattern and the single character O is a pattern.
• We then note that XO is a pattern since, according to rule 3a, it
is a sequence of the pattern
X followed by the pattern O.
• Finally, we note that XOXO is a pattern, according to rule 3a,
since it is a sequence of the pattern XO followed by the pattern
XO.
Write rules for the pattern in Credit Card Number
“1234-4567-3421-6789”.
Department of CSE,Coimbatore
Repetition Rules
• Repetitions allow us to more concisely rewrite the social security pattern.
• We recognize that a Social Security number follows the pattern of three
digits, two digits, and finally four digits.
• Since the numbers 3, 2, and 4 denote an exact number of repetitions we
may use rule 4d to generate a repeating pattern of digits.
• Social Security Pattern
(0|1|2|3|4|5|6|7|8|9) (0|1|2|3|4|5|6|7|8|9)
(0|1|2|3|4|5|6|7|8|9)- (0|1|2|3|4|5|6|7|8|9)
(0|1|2|3|4|5|6|7|8|9)- (0|1|2|3|4|5|6|7|8|9)
(0|1|2|3|4|5|6|7|8|9) (0|1|2|3|4|5|6|7|8|9)
(0|1|2|3|4|5|6|7|8|9)
Figure: Social Security pattern using only the basic rules

Department of CSE,Coimbatore
Repetition Rules contd---
• Figure: Repetition rules shows how we can rewrite the Social Security
number pattern using repetition rules.
• At the beginning of this pattern we use rule 4d to express that a Social
Security number must begin with exactly three digits.
• Following this we express that a dash must be present after which, according
to rule 4d, there must be exactly two digits.
• Finally, the pattern must end with a dash followed by exactly four digits.

Figure: Repetition
rules

Department of CSE,Coimbatore Identify the repetition rules in the string “ XOXOXOXOXO”

What has been described?
• How operations can be performed on strings.
• How to process textual information.
• How computers can be used to create, process, and
reason about textual information.
• How to recognize patterns.
• How to rewrite string literals as patterns.

Credits
Google images

Department of CSE,Coimbatore