Database annotation and retrieval

• US 20030177108A1
• Filed: 03/07/2003
• Published: 09/18/2003
• Est. Priority Date: 09/29/2000
• Status: Active Grant

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Garner, Philip Neil, Charlesworth, Jason Peter Andrew
• Granted Patent: US 7,240,003 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• 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. Data defining a lattice comprising:

data for defining a plurality of 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; and

data for arranging the nodes in a sequence of 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.

2. Data according to claim 1, wherein said data defines a plurality of time ordered nodes and wherein said data arranges the nodes in a sequence of time-ordered blocks.

3. Data according to claim 1 or 2, further comprising data defining information entries associated with said nodes and/or said links.

5. Data according to any preceding claim, wherein the links from nodes in any given block do not extend beyond the nodes in the succeeding block.

6. Data according to claim 5, further comprising:

data for defining 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.

7. Data according to claim 6, further comprising:

data for defining a second timing or nodal point (a) for each block identifying the earliest node in the block from which a link extends into the succeeding block.

8. Data according to claim 7, wherein the data for each node and its link or links is arranged as a sequence of data, and said sequences of data for respective nodes are arranged together in a datastream in an order corresponding to the time-ordering of the nodes.

9. Data according to any preceding claim, wherein for the nodes having a plurality of links, the data for each of those links is arranged in a predetermined manner dependent upon the extent of the corresponding links.

10. Data according to claim 9 when dependent upon claim 8, wherein for the nodes having a plurality of links, the data for the longest link is always positioned in a same relative position compared to the other links of the plurality of links within the sequence of data.

11. Data according to claim 10, wherein the data for the longest link is always positioned first or always positioned last amongst the plurality of links in each of the sequences of data.

12. Data according to any preceding claim, for use in a database, further comprising data defining each block'"'"'s location within said database.

13. Data according to any preceding claim, further comprising data defining time stamp information for each of said nodes.

19. An apparatus for searching a database comprising data according to any of claims 4 to 18, 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.

20. An apparatus according to claim 19, 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.

21. A method of searching a database comprising data according to any of claims 4 to 18, 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.

22. A method according to claim 21, further comprising the steps of generating word data corresponding to the user'"'"'s input query and searching the phoneme and word lattice using the word data generated for the input query.

44. An apparatus for adding data corresponding to one or more phonemes or words to the data defining a phoneme and/or word lattice according to any of claims 4 to 18, the apparatus comprising:

i) node processing means for inserting a node or nodes into the lattice by determining if a node already exists in the lattice, for the start and end times of a phoneme or word to be added, and inserting in the lattice a node or nodes corresponding to the start and/or end time if they do not already exist;

ii) link processing means for adding a link between the nodes corresponding to the start and end times for the phoneme or word to be added;

iii) selecting means for selecting which existing nodes possibly have associated link data that needs to be altered due to insertion of the further node or nodes;

iv) analysing means for analysing the link data of the selected existing nodes; and

v) means for altering the analysed link data if required;

wherein the selecting means is operable to select, for each further node, the nodes preceding the further node in the block containing the further node and also all the nodes in each of the blocks which precede the block containing the further node by a number of blocks equal to or less than the predetermined number of blocks.

45. An apparatus according to claim 44, wherein the selecting means is operable to select, for a further node to be inserted into a given block, only i) the nodes in the given block that precede the node being inserted, and ii) all the nodes in the preceding block.

46. An apparatus according to claim 44, wherein the data is as claimed in claim 7, and wherein the selecting means is operable to select, for a further node to be inserted into a given block at an insertion position defined by a timing or nodal point, the following:

a) if the insertion position is after the first timing or nodal point (β

) of the given block, only the existing nodes in the given block that precede the insertion position; and

b) if the insertion position is before the first timing or nodal point (β

) of the given block, only i) the existing nodes in the given block that precede the insertion position, and ii) those nodes in the preceding block that are at or after the second timing or nodal point (α

) of the preceding block.

47. An apparatus according to any of claims 44 to 46, wherein the data is according to claim 9 or any claim dependent thereon, and wherein the analysing means is arranged to analyse only the longest link extending from each selected node.

70. A method of adding data corresponding to one or more phonemes or words to the data defining a phoneme and/or word lattice according to any of claims 4 to 18, the method comprising the steps of:

i) inserting a node or nodes into the lattice by determining if a node already exists in the lattice, for the start and end times of a phoneme or word to be added, and inserting in the lattice a node or nodes corresponding to the start and/or end time if they do not already exist;

ii) adding a link between the nodes corresponding to the start and end times for the phoneme or word to be added;

iii) selecting which existing nodes possibly have associated link data that needs to be altered due to insertion of the further node or nodes;

iv) analysing the link data of the selected existing nodes; and

v) altering the analysed link data if required;

wherein the selecting step selects, for each further node, the nodes preceding the further node in the block containing the further node and also all the nodes in each of the blocks which precede the block containing the further node by a number of blocks equal to or less than the predetermined number of blocks.

71. A method according to claim 70, wherein the selecting step selects, for a further node to be inserted into a given block, only i) the nodes in the given block that precede the node being inserted, and ii) all the nodes in the preceding block.

72. A method according to claim 70, wherein the data is as claimed in claim 7, and wherein the selecting step selects, for a further node to be inserted into a given block at an insertion position defined by a timing or nodal point, the following:

a) if the insertion position is after the first timing or nodal point (β

) of the given block, only the existing nodes in the given block that precede the insertion position; and

b) if the insertion position is before the first timing or nodal point (β

) of the given block, only i) the existing nodes in the given block that precede the insertion position, and ii) those nodes in the preceding block that are at or after the second timing or nodal point (α

) of the preceding block.

73. A method according to any of claims 70 to 72, wherein the data is according to claim 9 or any claim dependent thereon, and wherein the analysing step analyses only the longest link extending from each selected node.

75. A data carrier carrying data according to any of claims 1 to 18 or processor-implementable instructions for controlling a processor to implement the method of any of claims 21, 22 and 49 to 74.

76. processor-implementable instructions for controlling a processor to implement the method of any of claims 21, 22 and 49 to 74.

4. Data defining a phoneme and/or word lattice for use in a database, the 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.

14. Data according to claim 4, further comprising data defining time stamp information for each of said nodes and wherein said data defining a phoneme and word lattice is associated with further data defining a time sequential signal, and wherein said time stamp information is time synchronised with said time sequential signal.

15. Data according to claim 14, wherein said further data defines an audio and/or video signal.

16. Data according to claim 15, wherein said further data defines at least speech data and wherein said data defining said phoneme and word lattice is derived from said further data.

17. Data according to claim 16, wherein said speech data comprises audio data and wherein said data defining said phoneme and word lattice is derived by passing said audio signal through an automatic speech recognition system.

18. Data according to claim 16 or 17, wherein said speech data defines the parol of a plurality of speakers, and wherein said data defines a separate phoneme and word lattice for the parol of each speaker.

23. 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.

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

25. An apparatus according to claim 23 or 24, wherein the first generating means comprises processing means for forming the phoneme and/or word lattice by processing the node data for each node and the link data for each link, the processing means comprising:

i) means for 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) first determining means for determining that the current block can be split in accordance with said block criteria; and

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

26. An apparatus according to claim 25, 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.

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

28. An apparatus according to claim 26, 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.

29. An apparatus according to claim 28, 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.

30. An apparatus according to any of claims 25 to 29, further comprising second determining means for 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 first determining means 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 splitting means is operable to split the current block responsive to the first determining means determining that the current block of nodes can be split.

31. An apparatus according to claim 30, wherein the second determining means 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.

32. An apparatus according to claim 30 or 31, wherein the splitting means is operable to split the current block between the first timing or nodal point (β

) and the second timing or nodal point (α

).

33. An apparatus according to claim 30 or claim 31, wherein the splitting means 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.

34. An apparatus according to claim 30 or claim 31, wherein the splitting means 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 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 splitting means 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.

35. An apparatus according to any of claims 23 to 34, further comprising sixth generating means for generating the phoneme and/or word data from input audio or text data.

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

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

38. An apparatus according to claim 35, wherein the data file comprises text data, and the sixth generating means comprises a text-to-phoneme converter for generating phoneme data from text data in the data file.

39. An apparatus according to claim 32, wherein the sixth generating means comprises one of the following group:

a) means for receiving and processing an input voice annotation signal;

b) means for receiving and processing a text annotation; and

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

40. An apparatus according to any of claims 23 to 39, wherein said first generating means is operable to generate data defining time stamp information for each of said nodes.

41. An apparatus according to any of claims 23 to 40, wherein said first generating means is operable to generate data which defines each block'"'"'s location within the database.

42. An apparatus according to claim 40 or 41, wherein said data file includes a time sequential signal, and wherein said first generating means is operable to generate time stamp data which is time synchronised with said time sequential signal.

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

48. An apparatus according to any of claims 23 to 43, further comprising an apparatus according to any of claims 44 to 47 for adding data corresponding to one or more phonemes or words to be added to the previously received phoneme and word data.

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

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.

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

51. A method according to claim 49 or 50, 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.

52. A method according to claim 51, 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.

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

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

55. A method according to claim 54, 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.

56. A method according to any of claims 51 to 55, 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.

57. A method according to claim 56, further comprising updating the first timing or nodal point (β

) and the second timing or nodal point (α

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

58. A method according to claim 56 or 57, 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 (α

).

59. A method according to claim 56 or claim 57, 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.

60. A method according to claim 56 or claim 57, 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.

61. A method according to any of claims 49 to 60, further comprising the step of generating the phoneme and/or word data from input audio or text data.

62. A method according to claim 61, 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.

63. A method according to claim 61, 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.

64. A method according to claim 61, 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.

65. A method according to any of claims 49 to 64, further comprising generating data defining time stamp information for each of said nodes.

66. A method according to any of claims 49 to 65, further comprising generating data which defines each block'"'"'s location within the database.

67. A method according to claim 65 or 66, wherein said data file includes a time sequential signal, and wherein the generated time stamp data is time synchronised with said time sequential signal.

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

69. A method according to claim 49 or 50, 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 more 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 further 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.

74. A method according to any of claims 49 to 69, further comprising adding further data to the lattice using a method in accordance with any of claims 70 to 73.