Database annotation and retrieval

• US 7,240,003 B2
• Filed: 09/28/2001
• Issued: 07/03/2007
• Est. Priority Date: 09/29/2000
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Charlesworth, Jason Peter Andrew, Garner, Philip Neil
• Primary Examiner(s): Azad; Abul K.
• Application Number:
  US10/363,752
• Publication Number:
  US 20030177108A1
• Time in Patent Office: 2,104 Days
• Field of Search: None
• US Class Current: 704/254
• CPC Class Codes: G06F 16/3343 using phonetics
• CPC Class Codes: G06F 16/632 Query formulation
• CPC Class Codes: G06F 16/685 using automatically derived transcript of audio data, e.g. lyrics speech recognition G10L15/00
• CPC Class Codes: G06F 16/7844 using original textual content or text extracted from visual content or transcript of audio data

Abstract

A data structure is provided for annotating data files within a database. The annotation data comprises a phoneme and word lattice which allows the quick and efficient searching of data files within the database, in response to a user'"'"'s input query for desired information. The phoneme and word lattice comprises a plurality of time-ordered nodes, and a plurality of links extending between the nodes. Each link has a phoneme or word associated with it. The nodes are arranged in a sequence of time-ordered blocks such that further data can be conveniently added to the lattice.

Claims

1. An apparatus for searching a database, comprising data defining a phoneme and/or word lattice for use in the database, said data comprising data for defining a plurality of time-ordered nodes within the lattice, data for defining a plurality of links within the lattice, each link extending from a first node to a second node, data for associating a phoneme or a word with at least one node or link, and data for arranging the nodes in a sequence of time-ordered blocks so that links from nodes in any given block do not extend beyond the nodes in a block that is a predetermined number of blocks later in the sequence, in response to an input query, by a user, the apparatus comprising:

means for generating phoneme data corresponding to the user'"'"'s input query;

means for searching the phoneme and word lattice using the phoneme data generated for the input query; and

means for outputting search results in dependence upon the output from said searching means.

2. An apparatus according to claim 1, further comprising means for generating word data corresponding to the user'"'"'s input query and means for searching the phoneme and word lattice using the word data generated for the input query.

3. A method of searching a database, comprising data defining a phoneme and/or word lattice for use in the database, said data comprising data for defining a plurality of time-ordered nodes within the lattice, data for defining a plurality of links within the lattice, each link extending from a first node to a second node, data for associating a phoneme or a word with at least one node or link, and data for arranging the nodes in a sequence of time-ordered blocks so that links from nodes in any given block do not extend beyond the nodes in a block that is a predetermined number of blocks later in the sequence, in response to an input query by a user, the method comprising the steps of:

generating phoneme data corresponding to the user'"'"'s input query;

searching the phoneme and word lattice using the phoneme data generated for the input query; and

outputting search results in dependence upon the results of said searching step.

4. A method according to claim 3, further comprising the steps of generating word data corresponding to the users input query and searching the phoneme and word lattice using the word data generated for the input query.

5. An apparatus for generating annotation data for use in annotating a data file, the apparatus comprising:

a receiver operable to receive phoneme and/or word data; and

a first generator operable to generate annotation data defining a phoneme and/or word lattice corresponding to the received phoneme and/or word data;

wherein the first generator comprises;

a second generator operable to generate node data defining a plurality of time-ordered nodes within the lattice;

a third generator operable to generate link data defining a plurality of links within the lattice, each link extending from a first node to a second node;

a fourth generator operable to generate association data associating each node or link with a phoneme or word from the phoneme and/or word data; and

a fifth generator operable to generate block data for arranging the nodes in a sequence of time-ordered blocks fulfilling a block criteria in which links from nodes in any given block do not extend beyond the nodes in a block that is a predetermined number of blocks later in the sequence.

6. An apparatus according to claim 5, wherein the block criteria is that links from nodes in any given block do not extend beyond the nodes in the succeeding block.

7. An apparatus according to claim 5, wherein the first generator comprises a processor operable to form the phoneme and/or word lattice by processing the node data for each node and the link data for each link, the processor comprising:

i) an adder operable to add one or more nodes and associated link or links to a current block of the lattice until the number of nodes in the current block reaches a predetermined number;

ii) a first determiner operable to determine if the current block can be split in accordance with said block criteria; and

iii) a splitter operable to split the current block into at least two blocks of nodes.

8. An apparatus according to claim 7, operable to generate the node data and the link data in correspondence to the phoneme and/or word data separately for each phoneme and/or word.

9. An apparatus according to claim 8, operable to generate all the node data and all the link data prior to forming the phoneme and/or word lattice.

10. An apparatus according to claim 8, operable to add the node data and link data for each phoneme and/or word to the phoneme and/or word lattice incrementally as it is generated for each said phoneme and/or word.

11. An apparatus according to claim 10, operable to add the node data and link data incrementally by:

determining if a node already exists for the start and end times for the current phoneme or word being processed;

adding to the lattice a node or nodes corresponding to the start and/or end time if they do not already exist; and

adding a link between the nodes corresponding to the start and end times for the current phoneme or word being processed.

12. An apparatus according to claim 7, further comprising a second determiner operable to determine a first timing or nodal point (β

) for each block identifying the latest node in the block to which any link originating in the preceding block extends and a second timing or nodal point (α

) for each block identifying the earliest node in the block from which a link extends into the succeeding block; and

wherein the first determiner is operable to determine that the current block of nodes can be split in accordance with said block criteria by determining that the first timing or nodal point (β

) is before the second timing or nodal point (α

) and wherein the splitter is operable to split the current block responsive to the first determiner determining that the current block of nodes can be split.

13. An apparatus according to claim 12, wherein the second determiner is operable to update the first timing or nodal point (β

) and the second timing or nodal point (α

) for each block, on addition of further nodes to the lattice.

14. An apparatus according to claim 12, wherein the splitter is operable to split the current block between the first timing or nodal point (β

) and the second timing or nodal point (α

).

15. An apparatus according to claim 14, wherein the sixth generator comprises one of the following:

a) a processor operable to receive and process an input voice annotation signal;

b) a processor operable to receive and process a text annotation; and

c) a processor operable to receive image data representative of a text document and a character recognition unit for converting said image data into text data.

16. An apparatus according to claim 12, wherein the splitter is operable to split the current block by forming a new block starting at or near the first timing or nodal point (β

) of the preceding block and ending at or near the first timing or nodal point (β

) of the current block.

17. An apparatus according to claim 12, wherein the splitter is operable to split the current black by forming a new block starting at or near the first timing or nodal point (β

) of the preceding block and ending at or near the first timing or nodal point (β

) of the current block if the first timing or nodal point (β

) of the preceding block is later than the second timing or nodal point (α

) of the preceding block, whereas the splitter is operable to split the current block between the first timing or nodal point (β

) and the second timing or nodal point (α

) if the first timing or nodal point (β

) of the preceding block is earlier than the second timing or nodal point (α

) of the preceding block.

18. An apparatus according to claim 5, further comprising a sixth generator operable to generate the phoneme and/or word data from input audio or text data.

19. An apparatus according to claim 18, wherein the data file comprises audio data, and the sixth generator comprises an automatic speech recognition system for generating phoneme data for audio data in the data file.

20. An apparatus according to claim 19, wherein the sixth generator further comprises a word decoder for generating word data by identifying possible words within the phoneme data generated by the automatic speech recognition system.

21. An apparatus according to claim 18, wherein the data file comprises text data, and the sixth generator comprises a text-to-phoneme converter for generating phoneme data from text data in the data file.

22. An apparatus according to claim 5, wherein said first generator is operable to generate data defining time stamp information for each of said nodes.

23. An apparatus according to claim 22, wherein said data file includes a time sequential signal, and wherein said first generator is operable to generate time stamp data which is time synchronised with said time sequential signal.

24. An apparatus according to claim 23, wherein said time sequential signal is an audio and/or video signal.

25. An apparatus according to claim 5, wherein said first generator is operable to generate data which defines each block'"'"'s location within the database.

26. A method of generating annotation data for use in annotating a data file, the method comprising:

i) receiving phoneme and/or word data; and

ii) generating annotation data defining a phoneme and/or word lattice corresponding to the received phoneme and/or word data;

wherein the step of generating annotation data defining the lattice comprises;

generating node data defining a plurality of time-ordered nodes within the lattice;

generating link data defining a plurality of links within the lattice, each link extending from a first node to a second node;

generating association data associating each link or node with a phoneme or word from the phoneme and/or word data; and

generating block data for arranging the nodes in a sequence of time-ordered blocks fulfilling a block criteria in which links from nodes in any given block do not extend beyond the nodes in a block that is a predetermined number of blocks later in the sequence.

27. A method according to claim 26, wherein the block criteria is that links from nodes in any given block do not extend beyond the nodes in the succeeding block.

28. A method according to claim 26, wherein the step of generating annotation data defining the lattice comprises the following steps for forming the phoneme and/or word lattice by processing the node data for each node and the link data for each link:

i) adding one or more nodes and associated link or links to a current block of the lattice until the number of nodes in the current block reaches a predetermined number;

ii) determining that the current block can be split in accordance with said block criteria; and

iii) splitting the current block into at least two blocks of nodes.

29. A method according to claim 28, wherein the node data and the link data is generated in correspondence to the phoneme and/or word data separately for each phoneme and/or word.

30. A method according to claim 29, wherein all the node data and all the link data is generated prior to forming the phoneme and/or word lattice.

31. A method according to claim 29, wherein the node data and link data for each phoneme and/or ward is added to the phoneme and/or word lattice incrementally as it is generated for each said phoneme and/or word.

32. A method according to claim 31, wherein the node data and link data is added incrementally by:

determining if a node already exists for the start and end times for the current phoneme or Word being processed;

adding to the lattice a node or nodes corresponding to the start and/or end time if they do not already exist; and

adding a link between the nodes corresponding to the start and end times for the current phoneme or word being processed.

33. A method according to claim 28, further comprising determining a first timing or nodal point (β

) for each block identifying the latest node in the block to which any link originating in the preceding block extends and a second timing or nodal point (α

) for each block identifying the earliest node in the block from which a link extends into the succeeding block; and

wherein the step of determining that the current block of nodes can be split in accordance with said block criteria comprises determining that the first timing or nodal point (β

) is before the second timing or nodal point (α

) and wherein the current block is split into the at least two blocks in response to it being determined that the current block of nodes can be split.

34. A method according to claim 33, further comprising updating the first dining or nodal point (β

) and the second timing or nodal point (α

) for each block, on addition of further nodes to the lattice.

35. A method according to claim 33, wherein the step of splitting the current block comprises splitting the current block between the first timing or nodal point (β

) and the second timing or nodal point (α

).

36. A method according to claim 33, wherein the step of splitting the current block comprises forming a new block starting at or near the first timing or nodal point (β

) of the preceding block and ending at or near the first timing or nodal point (β

) of the current block.

37. A method according to claim 33, wherein the step of splitting the current block comprises forming a new block starting at or near the first timing or nodal point (β

) of the preceding block and ending at or near the first timing or nodal point (β

) of the current block when the first timing or nodal point (β

) of the preceding block is later than the second timing or nodal point (α

) of the preceding block, whereas it comprises splitting the current block between the first timing or nodal point (β

) and the second timing or nodal point (α

) if the first timing or nodal point (β

) of the preceding block is earlier than the second timing or nodal point (α

) of the preceding block.

38. A method according to claim 26, further comprising toe step of generating the phoneme and/or word data from input audio or text data.

39. A method according to claim 38, wherein the data file comprises audio data, and the step of generating the phoneme and word data comprises:

using an automatic speech recognition system to generate phoneme data for audio data in the data file; and

using a word decoder to generate word data by identifying possible words within the phoneme data generated by the automatic speech recognition system.

40. A method according to claim 38, wherein the data file comprises text data, and the step of generating the phoneme and word data comprises using a text-to-phoneme converter to generate phoneme data from text data in the data file.

41. A method according to claim 38, wherein the step of generating the phoneme and/or word data comprises one of the following group:

a) receiving and processing an input voice annotation signal;

b) receiving and processing a text annotation; and

c) receiving image data representative of a text document and a character recognition unit for converting said image data into text data.

42. A method according to claim 26, further comprising generating data defining time stamp information for each of said nodes.

43. A method according to claim 42, wherein said data file includes a time sequential signal, and wherein the generated time stamp data is time synchronised with said time sequential signal.

44. A method according to claim 43, wherein said time sequential signal is an audio and/or video signal.

45. A method according to claim 26, further comprising generating data which defines each block'"'"'s location within the database.

46. A method according to claim 26, further comprising forming the phoneme and/or word lattice by processing the node data for each node and the link data for each link by;

i) adding node data for two nodes and link data for one or mote links therebetween;

ii) adding block data to provide an initial block of nodes constituted by the two added nodes;

iii) adding to the initial block of nodes further node data and/or link data for one or more thither nodes and/or links;

iv) repeating (iii) until the number of nodes in the initial block reaches a predetermined number of nodes;

v) determining that the initial block of nodes can be split in accordance with said block criteria;

vi) adding further block data to split the initial block of nodes into at least two current blocks of nodes;

vii) adding to one of the current blocks of nodes further node data and/or link data for one or more further nodes and/or links;

viii) repeating (vii) until the number of nodes in any current block is identified as reaching the predetermined number of nodes;

ix) determining that the identified current block can be split in accordance with said block criteria;

x) adding further block data to split the identified current block into at least two blocks;

xi) repeating (viii), (ix) and (x) if required until the node data and link data for all of the nodes and links generated for the phoneme and/or word data has been added to the phoneme and/or word lattice.

47. An apparatus for generating annotation data for use in annotating a data file, the apparatus comprising:

receiving means for receiving phoneme and/or word data; and

first generating means for generating annotation data defining a phoneme and/or word lattice corresponding to the received phoneme and/or word data;

wherein the first generating means comprises;

second generating means for generating node data defining a plurality of time-ordered nodes within the lattice;

third generating means for generating link data defining a plurality of links within the lattice, each link extending from a first node to a second node;

fourth generating means for generating association data associating each node or link with a phoneme or word from the phoneme and/or word data; and

fifth generating means for generating block data for arranging the nodes in a sequence of time-ordered blocks fulfilling a block criteria in which links from nodes in any given block do not extend beyond the nodes in a block that is a predetermined number of blocks later in the sequence.

48. A computer readable medium storing computer executable instructions for causing a programmable computer device to carry out a method of searching a database, comprising data defining a phoneme and/or word lattice for use in the database, said data comprising data for defining a plurality of time-ordered nodes within the lattice, data for defining a plurality of links within the lattice, each link extending from a first node to a second node, data for associating a phoneme or a word with at least one node or link, and data for arranging the nodes in a sequence of time-ordered blocks so that links from nodes in any given block do not extend beyond the nodes in a block that is a predetermined number of blocks later in the sequence in response to an input query by a user, the instructions comprising:

instructions for generating phoneme data corresponding to the user'"'"'s input query;

instructions for searching the phoneme and word lattice using the phoneme data generated for the input query; and

instructions for outputting search results in dependence upon the results of said searching step.

49. Computer executable instructions for causing a programmable computer device to carry out a method of searching a database, comprising data defining a phoneme and/or word lattice for use in the database;

said data comprising data for defining a plurality of time-ordered nodes within the lattice, data for defining a plurality of links within the lattice, each link extending from a first node to a second node, data for associating a phoneme or a word with at least one node or link, and data for arranging the nodes in a sequence of time-ordered blocks so that links from nodes in any given block do not extend beyond the nodes in a block that is a predetermined number of blocks later in the sequence, in response to an input query by a user, the instructions comprising;

instructions for generating phoneme data corresponding to the user'"'"'s input query;

instructions for searching the phoneme and word lattice using the phoneme data generated for the input query; and

instructions for outputting search results in dependence upon the results of said searching step.

50. A computer readable medium storing computer executable instructions for causing a programmable computer device to carry out a method of generating annotation data for use in annotating a data file, the computer executable instructions comprising:

instructions for receiving phoneme and/or word data; and

instructions for generating annotation data defining a phoneme and/or word lattice corresponding to the received phoneme and/or word data;

wherein the instructions for generating annotation data defining the lattice comprise;

instructions for generating node data defining a plurality of time-ordered nodes within the lattice;

instructions for generating link data defining a plurality of links within the lattice, each link extending from a first node to a second node;

instructions for generating association data associating each link or node with a phoneme or word from the phoneme and/or word data; and

instructions for generating block data for arranging the nodes in a sequence of time-ordered blocks fulfilling a block criteria in which links from nodes in any given block do not extend beyond the nodes in a block that is a predetermined number of blocks later in the sequence.

51. Computer executable instructions for causing a programmable computer device to carry out a method of generating annotation data for use in annotating a data file, the computer executable instructions comprising:

instructions for receiving phoneme and/or word data; and

instructions for generating annotation data defining a phoneme and/or word lattice corresponding to the received phoneme and/or word data;

wherein the instructions for generating annotation data defining the lattice comprise;

instructions for generating node data defining a plurality of time-ordered nodes within the lattice;

instructions for generating link data defining a plurality of links within the lattice, each link extending from a first node to a second node;

instructions for generating association data associating each link or node with a phoneme or word from the phoneme and/or word data; and

instructions for generating block data for arranging the nodes in a sequence of time-ordered blocks fulfilling a block criteria in which links from nodes in any given block do not extend beyond the nodes in a block that is a predetermined number of blocks later in the sequence.