Method and apparatus for caching VoiceXML documents

[0001] This invention relates to a method and apparatus for caching documents. In particular it relates to a method and apparatus in an interactive voice response system for caching VoiceXML documents.

[0002] A typical business interaction between a user and a business agent involves the agent talking to the user, asking questions, entering responses into a computer, and reading information to the user from a terminal screen. Such an interaction can be used to place a catalogue order; check an airline schedule; query a price; review an account balance; notify a customer; record and retrieve a message. For logical processes this can be automated by substituting the agent for an interactive voice response system (IVR) with an ability to play voice prompts and receive user input by speech recognition or from DTMF tones.

[0003] An interactive voice response system is typically implemented using a client server configuration where the telephony interface and voice application run on the client machine and voice data supply server software such as text-to-speech or a voice prompt database runs on a server with a local area network connecting the two machines. When the voice application requires voice data it requests a voice server to start streaming the voice data to the client. The client waits until a certain amount of voice data has been accumulated in a buffer and then plays voice data on an open telephony channel.

[0004] Voice applications used in an IVR can be written in VoiceXML markup language. VoiceXML is industry standard in the telephony market and grew from extensible markup language (XML). Through the use of customised tags VoiceXML offers greater flexibility in organising and presenting information than is possible with other mark up coding systems. VoiceXML defines a new set of XML ‘tags’ which can be used to write voice response applications and it simplifies speech application development by using familiar web infrastructure, including web pages, web tools and web servers.

[0005] Voice applications in the form of web pages are fetched and interpreted by a VoiceXML enabled browser which invokes the actions defined in the web page by the VoiceXML tags, e.g. play prompt; get DTMF; do voice recognition; play text-to-speech string etc. This allows people to embed VoiceXML tags in their existing HTML pages and effectively have a single source for both text and telephony based interaction with a server side application. The pages are simply served up to an IVR from a standard web server using the HTTP protocol in the same way as HTML pages would be. VoiceXML components such as a voice prompts are embedded in the VoiceXML application.

[0006] In a typical interactive voice system, a cache of a VoiceXML source code comprises a hash table of Universal Resource Indicator (URI) keys and associated filename entries. These entries are references to local files that exist in a known directory on the local machine. Each time a request is made to the cache for a document, the local file is loaded, its input stream is read, objects are created for each and every element in the document and processed in a hierarchical fashion.

[0007] For voice systems that use VoiceXML documents to describe dialogues with callers and support multiple telephone channels, there is a need to be able to efficiently cache VoiceXML documents for reuse across calls and across channels. Ordinarily a VoiceXML browser reads a raw input stream from a file and a VoiceXML parser generates a complete in-memory tree representation of the VoiceXML document. A schematic representation of the initial steps involved in prior art Document Object Model (DOM) creation follows:

[0008] Initial: DOCUMENT -read->INPUT STREAM -parse->DOM

[0009] Therefore current implementations store the source form of the VoiceXML document and require the VoiceXML interpreter to re-parse the document before use on each and every call. The problem with this process is that it is slow and is repeated every time a document is loaded regardless of whether it has been previously loaded.

[0010] According to a first aspect of the present invention there is provided a method of processing a mark-up language document prior to interpretation by a browser: receiving a mark-up document from a remote server; constructing a hierarchical structure of the constituent parts of the document for interpretation by a browser; storing the hierarchical structure and the constituents parts in local memory whereby next time the constructed document structure and parts are required for interpretation it is retrieved from local memory rather than constructed again from the source code.

[0011] The document is suitably a VoiceXML document and the hierarchical and constituent parts are a document object model (DOM). For instance, in the VoiceXML embodiment, time is saved by caching the entire DOM structure. The first time a document is loaded, the DOM tree is constructed as before. At this time the DOM tree is stored in a cache so that the next time the document is required, the DOM object is retrieved directly from cache. A schematic representation of the steps involved in DOM creation follows:

[0012] Initial retrieval: DOCUMENT -request->CACHE -not present->INPUT STREAM -parse->DOM -put in cache->CACHE

[0013] Subsequent retrieval: DOCUMENT -request->CACHE -present->DOM

[0014] Such caching of the DOM cuts out the expensive overhead of parsing a VoiceXML document each time it needs to be loaded into memory. This method saves time in making a DOM tree available but it can take significant space when stored in cache. A VoiceXML application can be extremely big and storing a DOM object in cache would consume a large amount of memory resource. Multiple VoiceXML documents would consume even more memory and could reduce that memory available for processing.

[0015] Instead of caching the whole DOM tree, fragments of the structure may be cached. In this way the browser benefits from an improvement in processing time and a cache populated by reusable DOM fragments. The DOM tree can be constructed from these fragments because the attributes and text can be separated from VoiceXML logic (or instructions) and set later. A schematic representation of the steps involved in DOM creation with fragments follows:

[0016] Initial retrieval: DOCUMENT -request->CACHE -not present->INPUT STREAM -parse->DOM -fragment->DOM FRAGMENTS -put in cache->FRAGMENT CACHE

[0017] Subsequent retrieval: DOCUMENT -request->CACHE -present->FRAGMENT CACHE -construct->DOM (NO ATTRS OR TEXT) -set attrs & text->DOM

[0018] An object in a DOM is the smallest data in the DOM. A fragment is a collection of objects and in particular all objects at a particular processing level or level within the DOM hierarchy. Both objects and fragments are consituent parts.

[0019] Advantageously the step of storing the hierarchical structure and constituent parts comprises checking the local memory for any pre-stored parts which are the same as the constituent parts; and storing in local memory only those constituent parts having no pre-stored equivalent whereby local memory does not store replicas of parts and local memory resource is maximised. This allows common parts in the same document and in other documents to be shared in the local memory space. This saves on memory when there is much commonality in the document or documents.

[0020] Advantageously the method further comprises associating a part with a unique reference which identifies equivalent parts. This unique reference is a numeric key derived from the actual elements that form the constituent part.

[0021] Preferably each constituent part contains a suitably sized collection of objects within the document object model, after being received from the remote server as a stream the document is constructed into a document object model; this document model next has its constituent parts identified; local memory is checked for any pre-stored parts that comprise of constructed objects using a unique numeric key reference; those constructed objects which are not pre-existing in local memory, that is a unique numeric key reference did not score a cache hit are then stored in local memory. This allows different documents to have common parts.

[0022] All documents are composed of a subset of elements that are processed in a routine fashion. There are only ever two degrees of freedom. These are attributes and text. These data sets are stored in a separate cache with the URI as the key reference. When these are eventually added to our constructed freeform objects, they recreate the original DOM object. All objects will have attribute properties and string data that require initialisation. Advantageously these freeform objects will be initialised after the DOM tree has been assembled from its constituent parts by traversing the hierarchical tree of objects and setting their attributes and data accordingly.

[0023] In addition, an instruction set should detail how to build the original DOM tree from its constituent parts. The instruction set is stored in a separate cache, again with the URI as the key reference. Advantageously, the DOM tree is assembled in a hierarchical fashion whereby root node objects are created and referenced pre-stored parts are appended to these nodes much like calling subroutines in a program. Caching in this manner means that storage is kept to a minimum but runtime performance is maximised. It is entirely possible that two URI references could have exactly the same instruction sets so there is scope for duplication.

[0024] The above solution increases cache performance by storing the objects directly in cache and setting them during runtime. It also reduces object storage allocation by creating fragment instruction sets.

[0025] The prior art solution stores the document object and its constituent element objects directly in cache by making them serializable and cloneable. The above approach reduces time taken to create these objects and reduces the space they consume in the cache due to duplication by separating the data (attrs, text) from the logic (or instructions) and storing them as cacheable fragments which can be retrieved and set quickly and easily.

[0031] Referring to the schematic overview of the present embodiment shown in FIG. 1. An interactive voice response (IVR) system 10 comprises a browser 12 and a parser 14. The browser 12 comprises an interpreter 16 and a platform 18. When the browser 12 is started after the IVR 10 connects with a telephone 20, it fetches the input stream from a VoiceXML document 22. Presently, this input stream is given to the parser 14 which in turn creates a Document Object Model (DOM) 24 which is a hierarchical tree representation of the VoiceXML document 22. The parser 14 traverses this tree and creates and initialises VoiceXML objects like an object factory. When a call comes in, these objects are executed to perform the appropriate telephony actions.

[0032] The parser 14 comprises: DOM tree 24; a DOM constructor 26; a DOM deconstructor 28; fragment cache 30; constructor cache 32; and content cache 34. Now, after the DOM tree has been constructed from document source code, it is deconstructed into fragment parts which can be used again. These fragment parts pertain to the hierarchical relationship that exist between the VoiceXML objects but are not initialised with content. The content is cached in the content cache 34; the instructions used to construct the original full tree is cached in the constructor cache 32. Each VoiceXML document 22 has a universal resource indicator (URI) for identification purposes. When the VoiceXML document 22 is loaded again, the browser uses its unique URI key to obtain the construction instructions for this document from the constructor cache 32. The DOM constructor 26 then rebuilds the tree of VoiceXML objects maintaining their hierarchical relationships. Next, these VoiceXML objects are initialised with the original content from the content cache 34. This content includes attributes and text. When a telephone call comes into the IVR 10 the objects are executed and performed just as if the DOM were assembled from scratch.

[0033] Referring to FIG. 2. The first pass through the browser 12 will be relatively slow as the DOM tree needs to be fetched, created and then deconstructed into fragment parts and stored (Steps 1 to 5). However, thereafter, the browser 12 can construct the tree from the cached information. This saves reading the input stream repeatedly (as in step 2) and creating VoiceXML objects (step 3) from scratch. The objects just require fetching (step 8) and initialisation (step 9) which is faster and more efficient than steps 1 to 5. The full sequence is described below:

[0034] step 1) a new document requested, the browser 12 requests a new VoiceXML document URI;

[0035] step 2) document source is fetched, input stream of the document source code is retrieved;

[0036] step 3) parser 14 creates DOM tree 24 from the document source, also the objects associated with each element of the DOM tree are created;

[0037] step 4) DOM is deconstructed into its fragment parts each of which contain their associated objects;

[0038] step 5) caching, fragment parts are cached, content (attributes and text) are cached, instructions for assembling are cached but parts which already exist in the cache are not cached again;

[0039] step 6) browser 12 executes the DOM, each object in the DOM which corresponds to a telephony action is executed;

[0040] step 7) a cached document is requested, the browser requests the cached VoiceXML document using the URI;

[0041] step 8) the cached objects are retrieved, the parser 14 retrieves the cached DOM constructor information for the document URI;

[0042] step 9) the DOM tree 24 is recreated from its constituent cached fragments and the original cached content is applied to their correctly associated objects; and

[0043] step 10) browser 12 executes DOM tree 24, each object in the DOM tree 24 which corresponding to a telephony action is executed.

[0044] FIG. 3 shows the DOM tree 24 for an example VoiceXML document, SimpleMenu.vxml, the source code of which follows:

[0045]

	<vxml version=“1.0”>
	<!-- This simple menu does not require text to speech
	or voice recognition capabilities. It plays an audio
	file and recognises DTMF input. -->
	<menu>
	<prompt>
	<audio src=“SimpleMenu.au” />
	</prompt>
	<choice dtmf=“1” next=“#end_menu” />
	</menu>
	<form id=“end_menu”>
	<block>
	<audio src=“EndMenu.au” />
	</block>
	</form>
	</vxml>

[0046] If we dissect the script, we have 1 attribute for <vxml> (that is ‘version=“1.0”’), 0 for menu, 0 for prompt, 1 for audio, etc. In this example there is no text for any elements. Vector translations are provided for both these data sets as follows:

• [0047] attributes={1, version=“1.0”, 0, 0, 1,
• [0048] src=“AnotherMenu.au”, 2, dtmf=“1”, next=“#end_menu”, 1,
• [0049] id=“end_menu”, 0}
• [0050] text={“ ”, “ ”, “ ”, “ ”, “ ”, “ ”, “ ”}

[0051] The reusable DOM fragments for this script are generated by splitting the overall tree into its constituent element siblings and caching them.

• [0052] frg1={prompt, audio}
• [0053] frg2={block, audio}
• [0054] frg3={menu, prompt, audio, choice}
• [0055] frg4={form, block, audio}

[0056] The cache entry for SimpleMenu.vxml would be {frg3, frg4}. So the next time SimpleMenu.vxml is requested, a new Document instance is created along with the root element which is “vxml”. The DOM fragments (frg3, frg4) are retrieved from the fragment cache and appended to the root element. Finally, the attributes and text strings are obtained from their corresponding caches and are applied to the tree by traversing it and making the changes.

[0057] The constructor cache 32 holds information on how to build the DOM tree 24 based on the document URI. In this case, the instructions are for creating a VoiceXML root element object (<vxml>) and attach fragment 1 (frg1) and fragment 2 (frg2) to this root element (<vxml>). The fragment cache 30 contains the skeleton VoiceXML objects (frg1 and frg2) and their relationships but not the content. Fragments 1 and 2 have unique URIs, are reusable within the same document or within multiple documents. The content cache 34 holds the attributes for each vxml element object. These are applied at the end of the process to complete the DOM tree.

[0058] Referring to FIG. 4 there is shown an example of the operation of the present embodiment for two similar VoiceXML applications. Consider two applications, SimpleMenu.vxml 22A and AnotherMenu.vxml 22B which are similar in structure but differ slightly in content. SimpleMenu.vxml refers to a different audio source in menu than AnotherMenu.vxml. AnotherMenu.vxml source code is shown below with the differences over SimpleMenu.vxml (shown above) underlined. IVR 10 loads SimpleMenu.vxml 22A first and parser 14 constructs DOM tree 24A and caches it. The second document, AnotherMenu.vxml 22B is then loaded. The DOM tree 24B of AnotherMenu.vxml is deconstructed by the parser 14 in the same way. Since it has the same VoiceXML structure to SimpleMenu.vxml, it will use the same fragments from fragment cache 30. However, it will store its own unique content separately in content cache 34 and its construction instructions in constructor cache 32. When multiple calls come in from telephones 20A, B, C they will request either SimpleMenu.vxml 22A or AnotherMenu.vxml 22B. The browser will now construct the DOM trees 24A and 24B from the cached information.

[0059]

	<vxml version=“1.0”>
	<!-- This menu does not require text to speech or voice
	recognition capabilities. It plays an audio file and
	recognises DTMF input. -->
	<menu>
	<prompt>
	<audio src=“AnotherMenu.au” />
	</prompt>
	<choice dtmf=“1” next=“#end_menu” />
	</menu>
	<form id=“end_menu”>
	<block>
	<audio src=“EndMenu.au” />
	</block>
	</form>
	</vxml>

[0060] For a large VXML document, an algorithm identifies as many fragments as it can within a DOM tree and splits it up accordingly. Splitting the tree up this way means that more fragments are likely to be shared. Also, by using fragments we are able to control the size of the fragment cache because we can dispose of unused fragments quite readily without affecting large DOM tree structures. The larger the VXML document the more likely it is to contain similar fragments and multiple VXML documents will also share similar fragments so the potential savings to both memory consumption and processing time would be great.