book2

Best algorithm for LZW ..C language

Alternatively, the last number can be stored for future re-dialling, freeing
the phone for other calls.
"Short code
dialling" allows a customer to associate short codes with commonly-dialled
numbers.
Alarm calls can be booked at specified times, and are made automatically
without human intervention.
Incoming calls can be barred, as can outgoing ones.  A diversion service
allows all incoming calls to be diverted to another telephone, either
immediately, or if a call to the original number remains unanswered for
a specified period of time, or if the original number is busy.
Three-party calls can be set up automatically, without involving the
operator.
.pp
Making use of these facilities presents the caller with something of a problem.
With conventional telephone exchanges, feedback is provided on what is happening
to a call by the use of four tones \(em the dial tone, the busy tone,
the ringing tone, and the number unavailable tone.
For the more sophisticated interaction which is expected on the advanced
exchange, a much greater variety of status signals is required.
The obvious solution is to use
computer-generated spoken
messages to inform the caller when these services are invoked, and to guide him
through the sequences of actions needed to set up facilities like call
re-direction.  For example, the messages used by the exchange when a user
accesses the alarm call
service are
.LB
.NI
Alarm call service.
Dial the time of your alarm call followed by square\u\(dg\d.
.FN 1
\(dg\d"Square" is the term used for the "#" key on the touch-tone telephone.\u
.EF
.NI
You have booked an alarm call for seven thirty hours.
.NI
Alarm call operator.  At the third stroke it will be seven thirty.
.LE
.pp
Because of the rather small vocabulary, the number of messages that can be
stored in their entirety rather than being formed by concatenation of
smaller units, and the short time which was available for development,
System\ X stores speech as a time waveform, slightly compressed by a time-domain
encoding operation (such techniques are described in Chapter 3).
Utterances which contain variable parts, like the time of alarm in the messages
above, are formed by inserting separately-recorded digits in a fixed 
"carrier" message.  No attempt is made to apply uniform intonation
contours to the synthetic utterances.  The resulting speech is of excellent
quality (being a slightly compressed recording of a human voice), but sometimes
exhibits somewhat anomalous pitch contours.
For example, the digits comprising numbers often sound rather jerky and
out-of-context \(em which indeed they are.
.pp
Even more advanced facilities can be expected on telephone exchanges in
the future.  A message storage capability is one example.  Although
automatic call recording machines have been available for years, a centralized
facility could time and date a message, collect the caller's identity
(using the telephone keypad), and allow the recipient to select messages left
for him through an interactive dialogue so that he could control the order
in which he listens to them.  He could choose to leave certain messages to be
dealt with later, or re-route them to a colleague.  He may even wish to leave
reminders for himself, to be dialled automatically at specified times (like
alarm calls with user-defined information attached).  The sender of a message
could be informed automatically by the system when it is delivered.  None of
this requires speech recognition, but it does need economical speech
.ul
storage,
and also speech
.ul
synthesis
(for time and date tags).
.sh "1.5  Travel consultant"
.pp
Some current research in speech communication with computers is aimed at
embedding the dialogue in a task environment which provides it with an overall
contextual framework.
This in fact was the motivation for the experimental telephone enquiry service
described above, and it was observed that people are able to tolerate rather
low quality speech if they feel that the interaction is worthwhile.  One step
further is the use of speech
.ul
input
as well as output, and here the context of the conversation which is provided
by the task environment can be used to improve recognition accuracy
significantly.
A system set up at Bell Telephone Laboratories indicates what we can expect
to find operating commercially in the future (Levinson and Shipley, 1980).
.[
Levinson Shipley 1980
.]
It provides timetable information about airline flights, and allows the user
to make reservations.
.pp
An example dialogue is given in Table 1.7.
.RF
.fi
.nh
.na
.in 0.3i
.nr x0 \w'COMPUTER:  '
.nr x1 \w'CALLER:  '
.in+\n(x0u
.ti-\n(x0u
COMPUTER:  This is the Bell Laboratories flight information system.  May I help you?
.ti-\n(x0u
CALLER:\h'\n(x0u-\n(x1u'  I would like to go to Chicago.
.ti-\n(x0u
COMPUTER:  Please specify the day of your departure.
.ti-\n(x0u
CALLER:\h'\n(x0u-\n(x1u'  I want to leave at four p.m..
.ti-\n(x0u
COMPUTER:  Please specify the day of your departure.
.ti-\n(x0u
CALLER:\h'\n(x0u-\n(x1u'  I want to depart on the two five May.
.ti-\n(x0u
COMPUTER:  Flight number nine two leaves New York at four p.m. arrives in Chicago at five twenty five p.m..
.ti-\n(x0u
CALLER:\h'\n(x0u-\n(x1u'  What plane is on the flight?
.ti-\n(x0u
COMPUTER:  The aircraft is a Boeing seven twenty seven.
.ti-\n(x0u
CALLER:\h'\n(x0u-\n(x1u'  How much is the fare?
.ti-\n(x0u
COMPUTER:  The round trip coach fare is one hundred forty two dollars.
.ti-\n(x0u
CALLER:\h'\n(x0u-\n(x1u'  I want a first class seat.
.ti-\n(x0u
COMPUTER:  One seat thank you.
.ti-\n(x0u
CALLER:\h'\n(x0u-\n(x1u'  What is the fare?
.ti-\n(x0u
COMPUTER:  The round trip first class fare is one hundred eighty four dollars.
.ti-\n(x0u
CALLER:\h'\n(x0u-\n(x1u'  Please repeat the arrival time.
.ti-\n(x0u
COMPUTER:  The arrival time is five twenty five p.m..
.ti-\n(x0u
CALLER:\h'\n(x0u-\n(x1u'  I will take the flight.
.ti-\n(x0u
COMPUTER:  Your reservation on flight number nine two to Chicago on Friday is confirmed.  Thank you.
.in 0
.nf
.MT 2
Table 1.7  A conversation with an airline flight information service
(from Levinson and Shipley, 1980)
.TE
.[
Levinson Shipley 1980
.]
The user dials the system from an
ordinary telephone.  The recognition side must be trained by each user, and
accepts isolated words spoken with brief pauses between them.
The voice response unit has a vocabulary of around 200 words, and
synthesizes its answers by slotting words into "templates" evoked by the speech
understanding part in response to a query.  For example,
.LB
.NI
This flight makes \(em stops
.NI
Flight number \(em leaves \(em at \(em , arrives in \(em at \(em
.LE
are templates which when called with specific slot fillers could produce the
utterances
.LB
.NI
This flight makes three stops
.NI
Flight number nine two leaves New York at four p.m.,
arrives in Chicago at five twenty-five p.m.
.LE
The chief research interest of the system is in its speech understanding
capabilities, and the method used for speech output is relatively
straightforward.  The templates and words are recorded, digitized, compressed
slightly, and stored on disk files (totalling a few hundred thousand bytes of
storage), using techniques similar to those of System\ X.
Again, no independent manipulation of pitch is possible, and so the utterances
sound intelligible but the transition between templates and slot fillers is not
completely fluent.  However, the overall context of the interaction means that
the communication is not seriously disrupted even if the machine occasionally
misunderstands the man or vice versa.  The user's attention is drawn away from
recognition accuracy and focussed on the exchange of information with the machine.
The authors conclude that progress in speech recognition can best be made by
studying it in the context of communication rather than in a vacuum or as part
of a one-way channel, and the same is undoubtedly true of speech synthesis as
well.
.sh "1.6  Reading machine for the blind"
.pp
Perhaps the most advanced attempt to provide speech output from a computer
is the Kurzweil reading machine for the blind, first marketed in the late
1970's (Figure 1.4).
.FC "Figure 1.4"
This device reads an ordinary book aloud.  Users adjust the reading
speed according to the content of the material and their familiarity with
it, and the maximum rate has recently been improved to around 225 words per
minute \(em perhaps half as fast again as normal human speech rates.
.pp
As well as generating speech from text, the machine has to scan the document
being read and identify the characters presented to it.  A scanning camera
is used, controlled by a program which searches for and tracks the lines of
text.  The output of the camera is digitized, and the image is enhanced
using signal-processing techniques.  Next each individual letter must be
isolated, and its geometric features identified and compared with a pre-stored
table of letter shapes.  Isolation of letters is not at all trivial, for
many type fonts have "ligatures" which are combinations of characters joined
together (for example, the letters "fi" are often run together.)  The
machine must cope with many printed type fonts, as well as typewritten ones.
The text-recognition side of the Kurzweil reading machine is in fact one of
its most advanced features.
.pp
We will discuss the problem of speech generation from text in Chapter 9.
It has many facets.  First there is pronunciation, the
translation of letters to sounds.  It is important to take into account
the morphological structure of words, dividing them into "root" and "endings".
Many words have concatenated suffixes (like "like-li-ness").  These are
important to detect, because a final "e" which appears on a root word
is not pronounced itself but affects the pronunciation of the previous
vowel.  Then there is the difficulty that some words look the same
but are pronounced differently, depending on their meaning or on the syntactic
part that they play in the sentence.
Appropriate intonation is extremely difficult to generate from a plain textual
representation, for it depends on the meaning of the text and the way in which
emphasis is given to it by the reader.  Similarly the rhythmic structure is
important, partly for correct pronunciation and partly for purposes of
emphasis.
Finally the sounds that have been deduced from the text need to be synthesized
into acoustic form, taking due account of the many and varied contextual effects
that occur in natural speech.  This by itself is a challenging problem.
.pp
The performance of the Kurzweil reading machine is not good.  While it seems
to be true that some blind people can make use of it, it is far from
comprehensible to an untrained listener.  For example,
it will miss out words and even whole phrases, hesitate in a
stuttering manner, blatantly mis-pronounce many words, fail to detect
"e"s which should be silent, and give completely wrong rhythms
to words, making them impossible to understand.
Its intonation is decidedly unnatural, monotonous, and often downright
misleading.  When it reads completely new text to people unfamiliar with its
quirks,
they invariably fail to understand more than an odd word here and there,
and do not improve significantly when the text is repeated more than once.
Naturally performance improves if the material is familiar or expected
in some way.
One useful feature is the machine's ability to spell out difficult words
on command from the user.
.pp
While not wishing to denigrate the Kurzweil machine, which is a remarkable
achievement in that it integrates together many different advanced
technologies, there is no doubt that the state of the art in speech synthesis
directly from unadorned text is extremely primitive, at present.
It is vital not to overemphasize the potential usefulness of abysmal speech,
which takes a great deal of training on the part of the user before
it becomes at all intelligible.  To make a rather extreme analogy,
Morse code could be used as
audio output, requiring a great deal of training, but capable of being understood
at quite high rates by an expert.
It could be generated very cheaply.
But clearly the man in the street would find it quite unacceptable as
an audio output medium, because of the excessive effort required to learn to use
it.  In many applications, very bad synthetic speech is just as useless.
However, the issue is complicated by the fact that for people who use
synthesizers regularly, synthetic speech becomes quite easily comprehensible.
We will return to the problem of evaluating the quality of artificial speech
later in the book (Chapter 8).
.sh "1.7  System considerations for speech output"
.pp
Fortunately, very many of the applications of speech output from computers
do not need to read unadorned text.
In all the example systems described above (except the reading machine),
it is enough to be able to store utterances in some representation which can
include pre-programmed cues for pronunciation, rhythm, and intonation in
a much more explicit way than ordinary text does.
.pp
Of course, techniques
for storing audio information have been in use for decades.
For example, a domestic cassette tape recorder stores speech at much better
than telephone quality at very low cost.  The method of direct
recording of an analogue waveform is currently used for announcements in
the telephone network to provide information such as the time, weather
forecasts, and even bedtime stories.
However, it is difficult to provide rapid access to messages stored in
analogue form, and although some computer peripherals which use analogue
recordings for voice-response applications have been marketed \(em they are
discussed briefly at the beginning of Chapter 3 \(em they have been
superseded by digital storage techniques.
.pp
Although direct storage of a digitized audio waveform is used in some
voice-response systems, the approach has certain limitations.  The most
obvious one is the large storage requirement:  suitable coding can reduce
the data-rate of speech to as little as one hundredth of that needed by
direct digitization, and textual representations reduce it by another factor
of ten or twenty.  (Of course, the speech quality is inevitably compromised
somewhat by data-compression techniques.)  However, the cost of storage is
dropping so fast that this is not necessarily an overriding factor.
A more fundamental limitation is that utterances stored directly cannot sensibly
be modified in any way to take account of differing contexts.
.pp
If the results of certain kinds of analyses
of utterances are stored, instead of simply the digitized waveform,
a great deal more flexibility can be gained.
It is possible to separate out the features of intonation and amplitude from
the articulation of the speech, and this raises the attractive possibility
of regenerating utterances with pitch contours different from those with which they were
recorded.