Today we're gonna talk about String Processing and we're gonna start by
talking about String Sorting. We'll take a look at some classic methods
but first we need to talk a little bit about just what strings are.
And actually, that's really It's dependent on the programming language that you're
using. It's different programming languages
nowadays really have completely different implementations of strings.
So to get started, we need to take a look at efficient implementations of basic
operations on strings. We're going to tailor our algorithms to
particular Java implementation, And that can be made to work in other
situations, But certainly, it's starting point, you
have to be specific. So what is a string?
A string is just a, sequence of characters, and it's actually a very
important fundamental attraction that's been with us from the beginning of the
information processing. So pretty much everything we communicate
is a string, email or our programs are strings.
But even, another important area of significance that has arisen recently is
in Computational Biology, where our understanding of the way that life works
depends on genomic sequences, and is essentially based on string processing.
We'll see examples of that later on. This is a quote that's talks about that
issue. The" digital information that underlies
biochemistry, cell biology and development can be represented by a simple string of
G's, A's, T's, and C's. This string is the root data structure of
an organisms biology. So we're not talking just about data
structures for information processing but for life models of life itself.
Now back to computers. The Strings are made up of characters.
What's a character? Well the kind of classical representation
of what a character is, is so called 7-bit ASCII Code.
Where you have actually the underlying data type is 8-bit so you coud have up to
256 characters. But for many, many years programmers used
only 128 of those characters that would include all the upper case and lower case
letters and numbers and some punctuation. So that's, 7-bit ASCII that's the standard
for the C programming language, that's a very widely used language.
Nowadays, people use what's called Unicode.
Where a character is a 16-bit integer. And that's to allow for many, many more
characters, Two to the sixteenth, 65,536 instead of
only 256. And that allows for encoding characters
from, many different of the world's lang-, languages, and mathematical characters.
So it's a much more, general and generous, representation of what is a character.
But it's important to, be specific. So, in Java, the standard is that a char
is a sixteen bit unsigned integer. Now, not all.
Programming systems and applications have moved up to the Unicode standard so
sometimes you'll find programs looking for Unicode encoding and not finding it,
And this t-shirt is a joke that has something to do that to do with that.
It's supposed to be a heart which is a valid Unicode character in some worlds,
but not on that t-shirt. So we'll come back to what is a character.
We're gonna use a simpler version in between those two, or characters in the
8-bit integer. Now let's talk about what a string is in
Java. There's a built-in string data type.
It's not quite built-in, but many of the features for processing string are built
into the Java language. So it's okay to think of it as being
built-in. And so in Java, a string is a sequence of
characters and it's immutable. Once you create a string, you can't change
it. And, the primary operations that you can
perform efficiently with a string are to, number one find it's length,
So you can get the length of the string. And that's just the number of characters
in it. You can index into a string and get the IT
character, that's the charAt method. And, you can eps, extract a substring of a
string, to create a new string, that's a continuous subsequence of the characters
in the string. And. one of the, big, features of Java's
implementation is that you can get that operation done in constant time,
And then you can also do what's called concatenation, and that's add a character
to the end of another string, That one can't be done in constant time in
the standard Java string data type. So, this is what the implementation looks
like for the string datat type in Java. The private instance variables are an
array of characters, An offset that's an index into the first
character of a string in the array the length and also to make it more efficient
to search using string keys java keeps a private variable which is the hashcode for
that string. So, once the string is built and the
hashcode computed, then when it's time to use the hashcode and the hashing algorithm
it's immediately available. So, the length method simply returns that
length. To get the IT character of the string, we
add I to the offset, and get that character.
And, to, create a string given an offset length and a character array, we just
reset those, values. And then the key thing is the substring,
method. Since all it involves is, a pointer into
the immutable string. And, a length, the index of the first
character we can build a string in, constant time just by copying the
reference to the character array. So that implementation we give good
feeling of why, you know, substring method is constant in string.
So this is the performance. It's a sequence of characters, is
immutable. And the underlying implementation is
immutable instance variables that give the array, offset and length.
And so it means that we can get length out of constant time, charAt in constant time
just by adding in the offset indexing. Substring in constant time just by
essentially cons, copying those instance variables.
But to concatenate, to make a new string that results from adding one character to
a string, we have to create a whole new string; and make a copy of it, because the
string itself is immutable So it takes time proportional to the number of
characters in the string, and it involves making a new string.
You can imagine string implementations, And they exist in various programming
languages, where, these performance guarantees are different.
And actually, Java has different implementations for applications where you
might want different performance, guarantees.
At the if you work out the memory usage for a string of length and it's 40 + 2N
bytes. You might consider using a char array, but
then you, you lose a lot of convenience. So, for being able to produce substring
and sublink, and also the language features that supports strings.
So here's an implementation of a different implementation of sequence of characters
in Java that is mutable. So it's, the idea is that you can use this
data type when you're building up a string a piece at a time.
Like maybe reading characters off standard input or something.
The underlying implementation in this case is a resizing array of characters.
So when it fills up and doubles, as we've done, many times before.
And it keeps the, the length that's an instance variable.
So with string builder, you can get the length in constant time.
You can get characters in constant time just by doubling, And you can concatenate,
add a new character in amortized constant time.
Most of the time, it's constant. Every once in a while, you might have to
double. But you pay for that double by, the number
of operations, that you did. The thing you lose though, is that it
takes linear time to extract a sub-string, because to extract a sub-string, you have
to make a new char array that can be re-sizing and so forth, and can be
immutable to concat So that's two different implementations of sequence of
characters in Java, where these two different, importantly different
performance characteristics, so we have to keep in mind be mindful of that in
applications, and again in other programming languages, something like the
StringBuilder is more like the standard, and you just have to know what the
implementation is. There's another one called StringBuffer as
well in Java that we will skip for now. So here's a typical example that might
have a simple computation like how do we efficiently reverse a string.
So you could use a string or you could use a StringBuilder with string you get to, a
declare it almost like a built-in type and simply initialize with the null string,
And then to rev-, rev-, compute the reverse string, we go backwards through
the original string and concatenate the, characters starting at the back to create
our reverse string. Or with the StringBuilder, you use, the
StringBuilder data type, And so it create an object, and that uses
the doubling array, And you use the append operation.
So, what do you think? Which one of these is, is gonna be, most
efficient for, a long string? The answer is, that it's StringBuilder
because the, using the built-in string every time you do a concatenation, you
have to make a copy of the whole string, so if the string is of length N, that's
gonna take, one + two + three all the way up to N, which sums to, N square, about
N^2/2 so it takes quadratic time to do a, for this algorithm to run, for a long
string. And that's gonna preclude using it for,
huge strings. as we've seen so many times, can't be using a quadratic time algorithm
for, lot of data. On the other hand, with StringBuilder it's
linear time because the append operations are amortized in linear.
So that's a simple example. Here's another example.
A computation that we're gonna look at later on at the end of the lecture is how
do we form an array of suffixes? So that is, we have an input string in the
suffixes of the string or the strings that you get by starting each position.
So the first suffix is the whole string, the next one starts at position one, the
next one starts at position two and so forth, each one less.
And so we have algorithms that gain efficiency by forming an array of suffixes
of a given, given string. And so how do we create that thing in the
first place? Again, you can do it with string or you
can do it with StringBuilder. so, let's look at it with string.
We get the length, that's gonna be the length of the array.
And what we do is for all values of I, we set suffixes of I to the sub string of X.
S you get by starting at I and going all the way to N and that's our suffix array
and this is the corresponding code for StringBuilder. But, now in this case the
standard method is gonna be linear. Whereas the StringBuilder, because there's
only one string and the sub-strings are a few pointers into that string.
Whereas for a StringBuilder, we have to make a new string for each suffix and
there's a quadratic number of characters in the, in all of those strings and so it
takes quadratic time, so you can't use StringBuilder to build a suffix array for
a huge string. So again, those are typical examples of
string processing where it really matters which string implementations that you're
using and if you're not using, if you're using Java, these trade-offs are clear.
If you're using some other programming language, you better make sure you know
how strings are implemented before you even get started with string processing.
So here's a simple computation that we'll be using.
Suppose that we have two strings and what we're interested in knowing is the length
of the longest common prefix. So here's some a static method that will
implement this function. Takes two strings as argument.
We're gonna need to go as far as the length of the shortest of the two strings,
So that's N. And then we just go ahead and start at the
beginning and compare as long as the strings are equal we increment I.
And if we get to a point where they're non-equal, that's when we return I.
And that's the length of the longest common pre-fixes.
In this case, they're not equal at four, that means they match at four characters.
And if we get to the end of one of them then that's a prefix,
So we just return N. So that's just a little bit of warm-up
code, and the amount of time that takes is proportional to the length of the longest
common prefix. Although if the prefix is short, like if
the two strings have a different first character, then it's a sublinear doesn't
have to look at all the data, just has to look at the amount that matches.
So, the idea of a sub-linear time algorithm for a string processing is a
really important one that, you know, we're going to be taking advantage of, as we
move into more complicated algorithms. So, for example, you can compare two
strings without looking at them all. It depends, you just have to find, the
first place that they differ, so you don't look at all the data at sub-linear time.
And we're going to see sorting algorithms that take advantage of that.
Now we're not gonna really do it, in the code that we show in lecture or even in
the book but it's actually fairly easy to take many of the algorithms that we're
gonna look at, and make some so that they work for general alphabets and for
different applications you know, it might be entirely appropriate to customize the
code to a particular alphabet. So, like if the, the thing are the things
that are being processed are numbers or positive integers,
Or things like account numbers, maybe only ten decimal characters can occur.
So, we might as well work with strings made from those well-defined ten
characters. In DNA, there's only four characters, so
we might as well know that we're working with four characters.
And so it's the we'll often talk of the radix, which is the number of possible
different character values in the string. Now we're always gonna use what's called
an Extended ASCII, where just to fix ideas, where the radix is 256.
And the number of. Bits, therefore to represent a character
is the log base two of that, so 8-bits, 256.
And when we talk about performance of algorithms, we'll use R and log, R just to
make sure that it's clear that if we're working with a smaller alphabet or a
larger alphabet we can still use the algorithms but the performance is going to
depend on the radix. So that's an introduction to String