[go: up one dir, main page]

WO2025177531A1 - 復号装置、復号方法、プログラム - Google Patents

復号装置、復号方法、プログラム

Info

Publication number
WO2025177531A1
WO2025177531A1 PCT/JP2024/006542 JP2024006542W WO2025177531A1 WO 2025177531 A1 WO2025177531 A1 WO 2025177531A1 JP 2024006542 W JP2024006542 W JP 2024006542W WO 2025177531 A1 WO2025177531 A1 WO 2025177531A1
Authority
WO
WIPO (PCT)
Prior art keywords
codebook
codeword
symbol string
analytic
tree
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
PCT/JP2024/006542
Other languages
English (en)
French (fr)
Inventor
亮介 杉浦
正彬 西野
宜仁 安田
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NTT Inc
NTT Inc USA
Original Assignee
Nippon Telegraph and Telephone Corp
NTT Inc USA
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Nippon Telegraph and Telephone Corp, NTT Inc USA filed Critical Nippon Telegraph and Telephone Corp
Priority to PCT/JP2024/006542 priority Critical patent/WO2025177531A1/ja
Publication of WO2025177531A1 publication Critical patent/WO2025177531A1/ja
Pending legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Definitions

  • the present invention relates to technology for lossless compression encoding of finite-precision digital signals and digital data.
  • Some lossless compression and encoding technologies output code words of a fixed length corresponding to an input symbol string.
  • the code words can be decoded at fixed lengths, which has the advantage of making it easier to handle data when performing calculations, searches, and other operations using the code words as they are without decoding.
  • the rules that indicate what codeword should be output for what symbol string are expressed using a parse tree or codebook. For example, in the case of an encoding rule that outputs a 3-bit codeword for a symbol string consisting of a combination of three symbols a, b, and c, it is desirable to assign a symbol string to each of the eight codewords that can be expressed in 3 bits and maximize the expected length of the symbol string encoded in 3 bits for a randomly given symbol string.
  • Figure 1 shows an example of a parse tree and codebook.
  • Figure 1(A) is an parse tree that represents an encoding rule that is effective when the occurrence probability of symbol a is high
  • the codebook in Figure 1(B) is equivalent to the parse tree in Figure 1(A).
  • the 3-bit codewords are assigned to the terminal nodes, or leaves, and each symbol that makes up the symbol string is assigned to an edge.
  • a single parse tree or codebook is used to obtain in parallel a symbol string ⁇ i corresponding to codeword w i , ... , w i+M-1 , and the symbol string ⁇ i ... ⁇ i+M-1 is output repeatedly. In this way, the time required for decoding the codewords w 0 w 1 ... w L-1 can be shortened.
  • ⁇ will represent a symbol string of length 0. Note that the symbol string ⁇ can be the prefix of any symbol string.
  • the codebook in the first embodiment is made up of pairs of an input symbol string and an output codeword of a predetermined length.
  • the decoding procedure in the first embodiment takes as input a codeword to be decoded (hereinafter referred to as an input codeword), obtains symbol strings corresponding to the codewords constituting the input codeword using two codebooks T0 and T1 (where the codebooks T0 and T1 are the codebooks used in the encoding procedure), and outputs a symbol string obtained by concatenating all the obtained symbol strings (hereinafter referred to as an output symbol string).
  • the codebook used to start encoding (hereinafter referred to as the starting codebook) is arbitrary, but information about which codebook was used to start encoding is shared between the encoding procedure and the decoding procedure.
  • the encoding procedure in the first embodiment is the same as the encoding procedure in Non-Patent Document 1.
  • the decoding procedure in the first embodiment is a parallel version of the decoding procedure in Non-Patent Document 1, and is different from the decoding procedure in Non-Patent Document 1.
  • the encoding procedure and decoding procedure are explained below.
  • the input symbol string is set as the current symbol string, and the starting codebook, T0 , is set as the current codebook.
  • the current codeword is the codeword currently being decoded, and the current codebook is the codebook currently being used for decoding. Therefore, the current codeword and current codebook at the start of decoding are the input codeword and the starting codebook, respectively.
  • the codebook switching rules i.e., the rules for determining which codebook to use next
  • the codebook switching rules are shared between the encoding procedure and the decoding procedure.
  • the decoding procedure in the first embodiment i.e., the decoding procedure when executed as parallel processing
  • M be a predetermined integer representing the unit of parallel processing (where M is an integer equal to or greater than 2).
  • the decoding procedure when executed as parallel processing consists of the following four processes (see FIG. 6 ):
  • compare codeword w i+j with the codewords contained in codebook T k and obtain the symbol string corresponding to codeword w i+j as candidate symbol string ⁇ (j, k). If a symbol string beginning with candidate symbol string ⁇ (j, k) (however, this symbol string is different from candidate symbol string ⁇ (j, k)) is not included in the set of symbol strings contained in codebook T k , obtain T 0 as the codebook to be used next; if it is included in the set, obtain T 1 as the codebook to be used next, and designate this next codebook as the candidate codebook T n(j, k) .
  • the decoding procedure when executed as parallel processing, can be said to consist of the following four processes.
  • compare codeword w j with the codewords contained in codebook T k and obtain the symbol string corresponding to codeword w j as candidate symbol string ⁇ (j, k). If a symbol string beginning with candidate symbol string ⁇ (j, k) (however, this symbol string is different from symbol string ⁇ (j, k)) is not included in the set of symbol strings contained in codebook T k , obtain T 0 as the codebook to be used next; if it is included in the set, obtain T 1 as the codebook to be used next, and designate this codebook to be used next as candidate codebook T n(j, k) .
  • the next codebook to be used is determined based on the codebook switching rules.
  • the encoding device 100 of this embodiment receives as input a symbol string to be encoded (hereinafter referred to as an input symbol string) and outputs a codeword corresponding to the input symbol string (hereinafter referred to as an output codeword).
  • the decoding device 200 of this embodiment receives as input a codeword to be decoded (hereinafter referred to as an input codeword) and outputs a symbol string corresponding to the input codeword (hereinafter referred to as an output symbol string).
  • a codeword is a string made up of two codes ⁇ 0, 1 ⁇ lined up in a row.
  • a symbol is an element of a set consisting of a finite number of elements, and can be text made up of letters or words, such as a, b, and c, which are elements of the alphabet set ⁇ a, b, c ⁇ .
  • a symbol string is a string made up of symbols lined up in a row, and for example, for two symbols ⁇ a, b ⁇ , abbaa is a symbol string of length 5.
  • the two codebooks or parse trees T 0 and T 1 used in the encoding process and the decoding process by the encoding device 100 and the decoding device 200 have data structures with the following characteristics.
  • the codebook in FIG. 5 is an example of the codebooks T 0 and T 1
  • the analytic tree in FIG. 2(A) is an example of the analytic trees T 0 and T 1 .
  • Fig. 7 is a block diagram showing the configuration of the encoding device 100.
  • Fig. 8 is a flowchart showing the operation of the encoding device 100.
  • the encoding device 100 includes an encoding unit 110 and a recording unit 190.
  • the recording unit 190 is a component that appropriately records information necessary for the processing of the encoding device 100.
  • the recording unit 190 records, for example, two codebooks or analytic trees T0 and T1 .
  • the encoding unit 110 obtains code words corresponding to the symbol strings that make up the input symbol string using two codebooks or parse trees T0 and T1 , and outputs the code word obtained by concatenating the obtained code words as the output code word.
  • the encoding unit 110 performs encoding processing consisting of the following three steps:
  • the current symbol string is compared with the symbol string contained in the codebook or parse tree, and a codeword corresponding to the symbol string ⁇ contained in the current codebook or parse tree that has the longest match with the prefix of the current symbol string is obtained.
  • the symbol string obtained by excluding the prefix that matches the symbol string ⁇ from the current symbol string is set as the current symbol string.
  • M is a predetermined integer representing the unit of parallel processing (where M is an integer greater than or equal to 2).
  • the decoding unit 210 obtains symbol strings corresponding to the code words that make up the input code word using two codebooks or parse trees T0 and T1 , and outputs the symbol string obtained by concatenating the obtained symbol strings as an output symbol string.
  • (2) A process in which M codewords of the same length as the lengths of the codewords contained in the two codebooks or parse trees T 0 and T 1 are obtained from the beginning of the current codeword, and the process in (2-1) is performed in parallel for the M codewords w j (j 0, ..., M-1).
  • T 1 If the symbol string is included in the set, T 1 as the codebook or analytic tree to be used next, and set the codebook or analytic tree to be used next as the candidate codebook or analytic tree Tn (j, k).
  • (3-1) Initializes counter j.
  • the process If the length of the current codeword is not 0, the process returns to (2). Otherwise, the process outputs the symbol string obtained by concatenating all symbol strings obtained by the process (3-2) as the output symbol string, and terminates the decoding process.
  • it is possible to reduce the time required for decoding using multiple codebooks or analytic trees. More specifically, by performing, in parallel for multiple codewords, the processes of obtaining candidate symbol strings corresponding to the codewords and candidate codebooks or analytic trees to be used next, it is possible to perform decoding using multiple codebooks or analytic trees while reducing the processing time required to obtain symbol strings corresponding to the codewords and the codebook or analytic tree to be used next.
  • the effect of the parallel processing is particularly significant when the size of the codebook or analytic tree is large and obtaining the symbol string requires a long processing time.
  • Non-Patent Document 1 which can express a coding rule that satisfies the unique codability condition.
  • a parse tree may be used instead of a codebook, and this does not result in any difference in the encoding procedure/decoding procedure.
  • the codebook in the second embodiment is composed of a triplet consisting of an input symbol string, an output codeword of a predetermined length, and the next codebook to be used (hereinafter referred to as a link destination).
  • FIG. 11 shows an example of a codebook.
  • the codebook in FIG. 11 is used to encode a symbol string of symbols ⁇ a, b, c ⁇ into a codeword of codes ⁇ 0, 1 ⁇ , and consists of five codebooks: T0 , T1 , T2 , T3 , and T4 . Note that the length of the codewords contained in codebooks T0 , T1 , T2 , T3 , and T4 is 2.
  • the expanded symbol string of that codebook begins with one of the symbol strings included in the symbol string mode assigned to that codebook.
  • the expanded symbol string of that analytic tree begins with one of the symbol strings included in the symbol string mode assigned to that analytic tree.
  • the current symbol string is the symbol string currently being encoded, and the current codebook is the codebook currently being used for encoding. Therefore, the current symbol string and the current codebook at the start of encoding are the input symbol string and the starting codebook, respectively.
  • the current codeword is the codeword currently being decoded, and the current codebook is the codebook currently being used for decoding. Therefore, the current codeword and current codebook at the start of decoding are the input codeword and the starting codebook, respectively.
  • This decoding procedure consists of the following three steps.
  • the codebook switching rules i.e., the rules for determining the next codebook to be used
  • the decoding procedure in the second embodiment i.e., the decoding procedure when executed as parallel processing
  • M be a predetermined integer representing the unit of parallel processing (where M is an integer equal to or greater than 2).
  • the decoding procedure when executed as parallel processing consists of the following four processes (see FIG. 6 ).
  • the encoding unit 110 performs encoding processing consisting of the following three steps:
  • the current symbol string is compared with the symbol strings included in the codebook or analytic tree.
  • M is a predetermined integer representing the unit of parallel processing (where M is an integer greater than or equal to 2).
  • the decoding unit 210 performs the decoding process, which consists of the following four steps:
  • the decoding unit 210 executes the decoding process consisting of the following four steps:
  • codebook or analytic tree T k (k is not any of k(0), ..., k(N-1)) to compare codeword w j with the codewords contained in the codebook or analytic tree T k , obtain the symbol string corresponding to codeword w j , and set codeword w j as the current codebook or analytic tree. (3-3) If j ⁇ M-1, increment counter j by 1 and return to process (3-2); otherwise, select the codeword obtained by removing the prefix that matches codeword w 0 ... w M-1 from the current codeword as the current codeword, and proceed to process (4).
  • candidate symbol strings may also be obtained using a portion of the codebook or parse tree.
  • processes (2-1) and (3-2) are as follows:
  • the embodiments of the present invention it is possible to reduce the time required for decoding using multiple codebooks or analytic trees. More specifically, by performing, in parallel, the process of obtaining candidate symbol strings corresponding to a plurality of codewords and candidate codebooks or analytic trees to be used next for the plurality of codewords, it becomes possible to perform decoding using a plurality of codebooks or analytic trees while shortening the processing time required to obtain the symbol strings corresponding to the codewords and the codebooks or analytic trees to be used next.
  • the effect of the parallel processing is particularly significant when the size of the codebooks or analytic trees is large and it takes a long processing time to obtain the symbol strings.
  • the codeword excluding the prefix that matches M-1 is set as the current codeword, and the process proceeds to (4).
  • the process returns to (2), otherwise the process outputs the symbol string obtained by concatenating all the symbol strings obtained by the process (3-2) as the output symbol string, and ends the decoding process.
  • the decoding unit 210 can be said to execute the following processes.
  • a process in which the input codeword is set as the current codeword, and the starting codebook or starting parse tree (where the starting codebook or starting parse tree is one of multiple codebooks or parse trees ⁇ T k ⁇ k 0 K-1 ) is set as the current codebook or parse tree.
  • codebook or analytic tree T k (k is not any of k(0), ..., k(N-1) ) , select codeword w j and the codebook or analytic tree T (3-3) A process of comparing the codewords included in k , obtaining a symbol string corresponding to codeword w j , obtaining the next codebook or parse tree to be used based on the codebook or parse tree switching rule, and setting the next codebook or parse tree to be used as the current codebook or parse tree. If j ⁇ M-1, increment counter j by 1 and return to process (3-2). Otherwise, a process of setting the codeword obtained by removing the prefix that matches codeword w 0 ...
  • FIG. 13 illustrates memory configurations during decoding.
  • FIG. 13A illustrates a memory (hereinafter referred to as the first memory) that stores the results of processing (2) performed in parallel in the decoding process of the first and second embodiments.
  • the first memory stores K symbol strings obtained using K codebooks for each codeword constituting a codeword to be decoded.
  • FIG. 13B illustrates a memory (hereinafter referred to as the second memory) that stores the results of processing (3) performed sequentially in the decoding process of the first and second embodiments.
  • the second memory stores a pair of an address indicating the start position of a storage area for a selected symbol string from among K symbol strings corresponding to a codeword to be decoded, and the length of the selected symbol string.
  • FIG. 13A illustrates a memory (hereinafter referred to as the first memory) that stores the results of processing (2) performed in parallel in the decoding process of the first and second embodiments.
  • the first memory stores K symbol strings obtained using K codebooks for each codeword constitu
  • 13B illustrates, for example, that a symbol string corresponding to codeword w i starting from the ith delimiter in the codeword to be decoded is stored in a storage area with address A t , and that the length of the selected symbol string is
  • the address in the first memory indicating the start position of the storage area for the symbol string ⁇ i in the second memory and the length of the symbol string ⁇ i are referenced
  • the start position of the storage area for the symbol string ⁇ i in the first memory is identified using the address
  • the range of the storage area for the symbol string ⁇ i is identified using the length of the symbol string ⁇ i , so that the symbol string ⁇ i can be referenced.
  • FIG. 13C shows the state of the second memory in this case.
  • the second memory stores a pair of an address indicating the start position of a storage area for a selected symbol string among K symbol strings corresponding to a codeword to be decoded, and the sum of the lengths of symbol strings selected up to the selected symbol string. This makes it possible to easily reference the p-th symbol in the output symbol string. Specifically, a symbol string including the p-th symbol can be referenced by specifying i such that S(i) ⁇ p ⁇ S(i+1).
  • the first memory stores symbol strings obtained by parallel processing using a single codebook for each codeword that constitutes the codeword to be decoded (see Figure 14(A)).
  • the second memory stores a pair of an address indicating the start position of a storage area for symbol strings corresponding to the codewords that constitute the codeword to be decoded, and the length of the symbol string. Note that if the storage areas for symbol strings are arranged at equal intervals in the first memory, it is possible to store only information about the length of the symbol string or the sum of the lengths of the symbol strings, as shown in Figure 14(B) or Figure 14(C).
  • the decoding device 200 in this embodiment receives as input a codeword to be decoded (hereinafter referred to as an input codeword), and obtains a symbol string corresponding to the codewords that constitute the input codeword.
  • the decoding device 200 may be configured to output a symbol string obtained by concatenating all of the obtained symbol strings as a symbol string corresponding to the input codeword (hereinafter referred to as an output symbol string).
  • Recording unit 290 also records, for example, information related to a starting codebook or starting analytic tree.
  • First memory 220 is a component that stores symbol strings obtained as symbol strings corresponding to codewords that constitute the input codeword using codebooks or analytic trees T 0 and T 1 .
  • the second memory 230 is a component that stores information about symbol strings obtained as symbol strings corresponding to code words that make up the input code word.
  • the present invention it is possible to reduce the time required for decoding using multiple codebooks or analytic trees. More specifically, by performing parallel processing for multiple codewords to obtain candidate symbol strings corresponding to the codewords and candidate codebooks or analytic trees to be used next, it is possible to perform decoding using multiple codebooks or analytic trees while reducing the processing time required to obtain symbol strings corresponding to the codewords and the codebook or analytic tree to be used next.
  • the effect of the parallel processing is particularly significant when the codebooks or analytic trees are large and obtaining the symbol strings requires a long processing time.
  • the second memory 230 is a component that stores information about symbol strings obtained as symbol strings corresponding to code words that make up the input code word.
  • M is a predetermined integer representing the unit of parallel processing (where M is an integer greater than or equal to 2).
  • the decoding unit 210 performs the decoding process, which consists of the following four steps:
  • (3-3) If j ⁇ M-1, increment counter j by 1 and return to process (3-2). Otherwise, a process of selecting codeword w 0 ... w The codeword excluding the prefix that matches M-1 is set as the current codeword, and the process proceeds to (4). (4) If the length of the current codeword is not 0, the process returns to (2), otherwise the process ends the decoding process. Note that in the process (3-2), the total length of the symbol strings obtained before the symbol string corresponding to codeword wj may be used instead of the length of the symbol string corresponding to codeword wj .
  • the codebook or analytic tree targeted in process (2) may be a codebook or analytic tree that is determined to be highly likely to be used, for example, based on the probability distribution of the occurrence of symbol strings.
  • candidate symbol strings may also be obtained using a portion of the codebook or parse tree.
  • the processes in (2-1) and (3-2) are as follows:
  • a codeword w j is compared with the codeword contained in the codebook or analytic tree T k , a symbol string corresponding to the codeword w j is obtained as a candidate symbol string ⁇ (j, k), and the candidate symbol string ⁇ (j, k) is stored in a storage area of the first memory 220 starting from a predetermined address.
  • a candidate symbol string ⁇ (j, k) is selected and obtained as a symbol string corresponding to codeword w j , and a pair of an address indicating the start position of a storage area in first memory 220 for a symbol string corresponding to codeword w j and the length of the symbol string corresponding to codeword w j is stored in second memory 230, a candidate codebook or candidate analytic tree T n(j, k) to be used next is selected and obtained as the codebook or analytic tree to be used next, and the codebook or analytic tree to be used next is set as the current codebook or analytic tree, otherwise, codebook T k (k is not k(0)) is used to compare codeword w j with the codeword contained in codebook or analytic tree T k to obtain a symbol string corresponding to codeword w j , and the symbol string corresponding to codeword w j is stored in a storage area in first memory 2
  • the present invention it is possible to reduce the time required for decoding using multiple codebooks or analytic trees. More specifically, by performing parallel processing for multiple codewords to obtain candidate symbol strings corresponding to the codewords and candidate codebooks or analytic trees to be used next, it is possible to perform decoding using multiple codebooks or analytic trees while reducing the processing time required to obtain symbol strings corresponding to the codewords and the codebook or analytic tree to be used next.
  • the effect of the parallel processing is particularly significant when the codebooks or analytic trees are large and obtaining the symbol strings requires a long processing time.
  • the decoding unit 210 in the third and fourth embodiments performs decoding processing using multiple codebooks or analytic trees based on a predetermined codebook or analytic tree switching rule. More specifically, the decoding unit 210 repeatedly performs processing consisting of the following two processes:
  • the process sequentially executes the following steps: Obtaining a pair of a symbol string corresponding to the codeword and a codebook or analytic tree to be used next based on a pair of a candidate symbol string obtained for the codeword and a candidate codebook or analytic tree to be used next, the current codebook or analytic tree, and a codebook or analytic tree switching rule; Storing a set of an address indicating the start position of a storage area for the symbol string corresponding to the codeword in the first memory 220 and the length of the symbol string corresponding to the codeword or the sum of the lengths of symbol strings obtained before the symbol string corresponding to the codeword in the second memory 230; and designating the codebook or analytic tree to be used next as the current codebook or analytic tree.
  • a candidate codebook or candidate analytic tree T n(j, k) to be used next is selected as the codebook or analytic tree to be used next, and the codebook or analytic tree to be used next is set as the current codebook or analytic tree. (3-3) If j ⁇ M-1, the counter j is incremented by 1, and the process returns to ( 3-2 ). Otherwise, the process (4) if the length of the current codeword is not 0, return to the process (2), otherwise terminate the decoding process.
  • a candidate symbol string ⁇ (j, k) is selected and obtained as a symbol string corresponding to a codeword w j , and a set of an address indicating the start position of a storage area for a symbol string corresponding to the codeword w j in the first memory and a length of the symbol string corresponding to the codeword w j or a total value of the lengths of symbol strings obtained before the symbol string corresponding to the codeword w j is stored in the second memory.
  • the expanded symbol string of the codebook or analytic tree T k satisfies the condition that it begins with any symbol string included in the symbol string mode assigned to the codebook or analytic tree T k , the process of obtaining the next codebook or analytic tree to be used based on the codebook or analytic tree switching rule is a process of obtaining the next codebook or analytic tree to be used corresponding to the codeword wj using a codebook or analytic tree Tk .
  • the program describing this processing can be recorded on a computer-readable recording medium.
  • Examples of computer-readable recording media include magnetic recording devices, optical disks, magneto-optical recording media, and semiconductor memory.
  • a computer that executes such a program for example, first stores the program recorded on a portable recording medium or transferred from a server computer in its own storage device. Then, when executing processing, the computer reads the program stored in its storage device and executes processing in accordance with the read program.
  • the computer may read the program directly from the portable recording medium and execute processing in accordance with that program, or it may execute processing in accordance with the received program each time a program is transferred to this computer from the server computer.
  • the server computer may not transfer the program to this computer, but rather executes processing using a so-called ASP (Application Service Provider) type service, which realizes processing functions simply by issuing execution instructions and obtaining results.
  • ASP Application Service Provider
  • the device is configured by executing a specific program on a computer, but at least part of the processing may also be implemented in hardware.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)

Abstract

復号部は、入力符号語を構成する複数の符号語に対して、複数の符号帳または解析木に含まれる１以上の所定の符号帳または解析木を用いて符号語に対応する記号列を候補記号列として得て、符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木として得る処理を並列に実行する処理と、入力符号語を構成する複数の符号語に対して、符号語に対して得られた候補記号列と次に使用する候補符号帳または候補解析木の組と、現在の符号帳または解析木と、符号帳または解析木の切り替え規則とに基づいて、当該符号語に対応する記号列と次に使用する符号帳または解析木の組を得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理を逐次実行する処理と、から構成される処理を繰り返し実行する。

Description

復号装置、復号方法、プログラム
　本発明は、有限精度のディジタル信号やディジタルデータを可逆に圧縮符号化する技術に関する。
　現在、音声信号、画像信号、輝度センサや加速度センサや地震計などの各種センサから得られた時系列信号、文字列、単語列などの有限精度のディジタル信号やディジタルデータを可逆に圧縮符号化する技術が開発されている。可逆に圧縮符号化する技術の中には、入力される記号列に対応する出力される符号語の長さを一定とするものがある。この場合、符号語を一定の長さ毎に復号することができるため、復号することなく符号語のまま計算や検索などの処理を実行する上でデータの取り扱いが容易になるという利点がある。
　可逆に圧縮符号化する技術を設計する場合、どのような記号列に対してどのような符号語を出力するかを表す規則（以下、符号化規則という）を解析木（parse tree）や符号帳を用いて表現する。例えば、３つの記号a, b, cの組み合わせで構成される記号列に対して３ビットの符号語を出力する符号化規則の場合、３ビットで表現できる８つの符号語それぞれに対して記号列を割り当て、ランダムに与えられる記号列に対して３ビットで符号化される記号列の長さの期待値を最大化することが望ましい。そのためには、記号a, b, c中で出現確率が高い記号がなるべく含まれる記号列に３ビットの符号語を割り当てて符号化規則を設計することが有効である。図１は解析木と符号帳の例を示す図である。図１(A)は記号aの出現確率が高いときに有効な符号化規則を表す解析木であり、図１(B)の符号帳は図１(A)の解析木と等価である。図１(A)の解析木では、３ビットの符号語は末端のノードである葉に、記号列を構成する各記号はエッジに割り当てられている。どのような記号列が入力されても一意に符号化できることを担保した方が圧縮効率のよい符号を構成することができる。そのような符号を構成するためには、図１(A)の解析木のように各ノードは子ノードを持たない（つまり葉である）か、記号の種類の数（本例ではa, b, cの３つ）の子ノードを持つかのいずれかである必要がある。
　しかし、上記ノードに関する制約条件は厳しいものであり、符号語の長さを一定とする符号では圧縮効率が上げにくいという傾向がある。例えば、図１の例において、記号aが記号b, cよりも非常に出現確率が高いとする。この場合、符号化できる記号列長の期待値を高めるためには記号aが連なる記号列aaaに対して符号語を割り当てることが効率的であるが、上記制約条件を満たすようにするため記号列aab, aacの出現確率があまり高くない場合であっても記号列aab, aacに対して符号語を割り当てる必要があり、記号列aab, aacの出現確率より記号列ba, caの出現確率の方が高い場合、出現確率に対する語長が短くなるおそれがある。そのため、限りある符号語を無駄にしてしまい、圧縮効率は下がってしまう。
　そこで、非特許文献１の技術では、複数の解析木を用いることで上記制約条件を緩和している。図２は解析木と符号帳の例を示す図である。図２(A)は図１(A)と等価な解析木であり、図２(B)の符号帳は図２(A)の解析木と等価である。図２(A)の解析木は２つの解析木T0, T1で１つの符号化規則を表している。解析木T0, T1では、符号語が葉以外のノードにも割り当てられている。葉以外のノードに割り当てられた符号語を出力した場合には解析木T1を用いて次の記号列を符号化し、葉に割り当てられた符号語を出力した場合には解析木T0を用いて次の記号列を符号化するといった解析木の切り替え規則を定めることにより、どのような記号列が入力されても一意に符号化できることを担保しながら圧縮効率を上げている。図２(A)の解析木では葉以外のノードについても符号語が割り当てられるため、ノードは記号の種類の数の子ノードを持つ必要がない。そのため、図２をみるとわかるように記号列aab, aacに符号語を割り当てる必要がなく、その代わりに記号列ba, caに符号語を割り当てることが可能となる。
H. Yamamoto, H.Yokoo, "Average-Sense Optimality and Competitive Optimality for Almost Instantaneous VF Codes," in IEEE Transactions on Information Theory, vol.47, no.6, pp.2174-2184, Sep. 2001.
　図１の技術のように、単一の解析木や符号帳を用いて符号化／復号を行う場合には、復号処理を並列化することが可能である。解析木や符号帳に含まれる符号語の長さは同じであるため、復号対象となる符号語における区切りは復号処理を開始する前からすべてわかる。したがって、復号対象となる符号語における区切りから始まる複数の符号語に対して並列に復号処理を実行することにより、復号処理を高速化することが可能となる。詳しく説明する。図３、図４は復号処理の例を示す図である。図３、図４は復号対象となる符号語w0w1…wL-1（ただし、wi(i=0, ..., L-1)は単一の解析木や符号帳に含まれる符号語と長さが同じ符号語）の復号処理のフローを示す図である。図３の復号処理では、符号語w0w1…wL-1に対して符号語w0から順にひとつずつ単一の解析木や符号帳を用いて符号語wiに対応する記号列σiを取得して出力することを繰り返す。一方、図４の復号処理では、M（Mは２以上の整数）を並列処理の単位とし、符号語w0w1…wL-1に対してM個の符号語wi, …, wi+M-1ごとに単一の解析木や符号帳を用いて符号語wiに対応する記号列σiを並列に取得して記号列σi…σi+M-1を出力することを繰り返す。このようにすることで、符号語w0w1…wL-1の復号処理にかかる時間を短縮することができる。
　なお、ここでいう並列処理は、並列処理の対象となる複数の処理すべてを同じタイミングで実行することに限定されるものではなく、ある処理が別の処理の終了前に開始される形で複数の処理が実行される場合も含む。
　非特許文献１の技術は単一の解析木や符号帳を用いて表される符号よりも圧縮効率の高い符号を構成することができるものの、図４のように復号処理を並列に実行することはできない。これは、複数の解析木や符号帳を用いて符号化／復号を行う場合には、復号対象となる符号語における区切りから始まる符号語を復号するために用いる解析木や符号帳を確定させるためには、当該符号語より前の符号語を復号して解析木や符号帳の切り替えの過程をたどる必要があるためである。
　そこで本発明では、復号処理にかかる時間を短縮することが可能な、複数の符号帳または解析木を用いた符号化／復号技術を提供することを目的とする。
　本発明の一態様は、復号対象となる符号語（以下、入力符号語という）を入力とし、当該入力符号語に対応する記号列（以下、出力記号列という）を出力する復号装置であって、複数の符号帳または解析木（ただし、当該複数の符号帳または解析木は前記入力符号語を得るための符号化処理で用いた複数の符号帳または解析木と同一である）を用いて前記入力符号語を構成する符号語に対応する記号列を得て、得られた記号列を連結して得られる記号列を前記出力記号列として出力する復号部を含み、前記複数の符号帳または解析木は、少なくとも記号列と符号語とを含む組から構成され、前記複数の符号帳または解析木に含まれる符号語はすべて長さが同じであり、前記復号部は、前記入力符号語を構成する複数の符号語に対して、前記複数の符号帳または解析木に含まれる１以上の所定の符号帳または解析木を用いて符号語に対応する記号列を候補記号列として得て、符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木として得る処理を並列に実行する処理と、前記入力符号語を構成する複数の符号語に対して、符号語に対して前記得られた候補記号列と次に使用する候補符号帳または候補解析木の組と、現在の符号帳または解析木と、前記符号帳または解析木の切り替え規則とに基づいて、当該符号語に対応する記号列と次に使用する符号帳または解析木の組を得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理を逐次実行する処理と、から構成される処理を繰り返し実行することにより、前記出力記号列を得る。
　本発明によれば、複数の符号帳または解析木を用いた復号処理にかかる時間を短縮ことが可能となる。
解析木と符号帳の例を示す図である。 解析木と符号帳の例を示す図である。 復号処理の例を示す図である。 復号処理の例を示す図である。 符号帳の例を示す図である。 復号処理の例を示す図である。 符号化装置１００の構成を示すブロック図である。 符号化装置１００の動作を示すフローチャートである。 復号装置２００の構成を示すブロック図である。 復号装置２００の動作を示すフローチャートである。 符号帳の例を示す図である。 解析木の例を示す図である。 復号処理におけるメモリの様子を示す図である。 復号処理におけるメモリの様子を示す図である。 復号装置２００の構成を示すブロック図である。 本発明の実施形態における各装置を実現するコンピュータの機能構成の一例を示す図である。
　以下、本発明の実施形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
　各実施形態の説明に先立って、この明細書における表記方法について説明する。
　^（キャレット）は上付き添字を表す。例えば、xy^zはyzがxに対する上付き添字であり、xy^zはyzがxに対する下付き添字であることを表す。また、_（アンダースコア）は下付き添字を表す。例えば、xy_zはyzがxに対する上付き添字であり、xy_zはyzがxに対する下付き添字であることを表す。
　ある文字xに対する^xや~xのような上付き添え字の”^”や”~”は、本来”x”の真上に記載されるべきであるが、明細書の記載表記の制約上、^xや~xと記載しているものである。
　以下、εは長さが0の記号列を表すものとする。ここで、記号列εは任意の記号列の語頭となりうることに留意する。
＜技術的背景＞
　第１実施形態における符号化／復号は、一意に符号化することができるという条件（以下、一意符号化可能性条件という）を満たす符号化規則を表現することができる非特許文献１の技術に基づく複数の符号帳を用いる。なお、符号帳の代わりに解析木を用いてもよく、符号化手順／復号手順に違いが生じることはない。
＜＜１：符号帳＞＞
　第１実施形態における符号帳は、入力となる記号列と出力となる所定の長さの符号語の２つ組から構成される。
　図５は符号帳の例を示す図である。図５の符号帳は非特許文献１の技術に基づく符号帳であり、図２(A)の解析木と等価である。図５の符号帳は記号{a, b, c}の列である記号列を符号{0, 1}の列である符号語に符号化するために用いるものであり、T0, T1の２つの符号帳からなる。符号帳T0, T1に含まれる符号語の長さは3であることに留意する。
＜＜２：符号化手順／復号手順＞＞
　第１実施形態における符号化手順は、符号化対象となる記号列（以下、入力記号列という）を入力とし、２つの符号帳T0, T1を用いて入力記号列を構成する記号列に対応する符号語を得て、得られたすべての符号語を連結して得られる符号語（以下、出力符号語という）を出力する。また、第１実施形態における復号手順は、復号対象となる符号語（以下、入力符号語という）を入力とし、２つの符号帳T0, T1（ただし、符号帳T0, T1は符号化手順で用いた符号帳）を用いて入力符号語を構成する符号語に対応する記号列を得て、得られたすべての記号列を連結して得られる記号列（以下、出力記号列という）を出力する。
　なお、符号化を開始する際に用いる符号帳（以下、開始符号帳という）は任意であるが、どの符号帳を用いて符号化を開始したのかという開始符号帳に関する情報は、符号化手順と復号手順の間で共有される。
　以下、図５の符号帳を例として符号化手順／復号手順について説明する。ここでは、開始符号帳を符号帳T0とする。
　第１実施形態における符号化手順は、非特許文献１における符号化手順と同じである。一方、第１実施形態における復号手順は、非特許文献１における復号手順を並列化したものであり、非特許文献１における復号手順と異なる。以下、符号化手順、復号手順について説明する。
（符号化手順）
　現在の記号列を現時点において符号化処理の対象である記号列、現在の符号帳を現時点において符号化処理に用いるべき符号帳とする。したがって、符号化を開始した時点における現在の記号列、現在の符号帳はそれぞれ入力記号列、開始符号帳である。
　第１実施形態における符号化手順は以下の３つの処理からなる。
（１）入力記号列を現在の記号列とする。また、開始符号帳であるT0を現在の符号帳とする。
（２）現在の符号帳を用いて、現在の記号列と当該符号帳に含まれる記号列を比較する。現在の記号列の語頭と最も長く一致する、現在の符号帳に含まれる記号列σに対応する符号語を得て、現在の記号列から当該記号列σと一致した語頭を除いた記号列を現在の記号列とする。また、記号列σを語頭とする記号列（ただし、当該記号列は記号列σと異なる）が、現在の符号帳に含まれる記号列の集合に含まれない場合はT0を次に使用する符号帳として得て、当該集合に含まれる場合はT1を次に使用する符号帳として得て、当該次に使用する符号帳を現在の符号帳とする。
（３）現在の記号列の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は（２）の処理により得られたすべての符号語を連結して得られる符号語を出力符号語として出力し符号化処理を終了する。
（復号手順）
　現在の符号語を現時点において復号処理の対象である符号語、現在の符号帳を現時点において復号処理に用いるべき符号帳とする。したがって、復号を開始した時点における現在の符号語、現在の符号帳はそれぞれ入力符号語、開始符号帳である。
　まず、非特許文献１における復号手順、すなわち、並列処理として実行しない場合における復号手順を示す。当該復号手順は以下の３つの処理からなる。
（１）入力符号語を現在の符号語とする。また、開始符号帳であるT0を現在の符号帳とする。
（２）現在の符号帳を用いて、現在の符号語と当該符号帳に含まれる符号語を比較する。現在の符号語の語頭と一致する、現在の符号帳に含まれる符号語wに対応する記号列を得て、現在の符号語から当該符号語wと一致した語頭を除いた符号語を現在の符号語とする。また、符号語wに対応する記号列を語頭とする記号列（ただし、当該記号列は符号語wに対応する記号列と異なる）が、現在の符号帳に含まれる記号列の集合に含まれない場合はT0を次に使用する符号帳として得て、当該集合に含まれる場合はT1を次に使用する符号帳として得て、当該次に使用する符号帳を現在の符号帳とする。
（３）現在の符号語の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は（２）の処理により得られたすべての記号列を連結して得られる記号列を出力記号列として出力し復号処理を終了する。
　ここで、符号化手順における（２）の処理と復号手順における（２）の処理とを比較すると、符号化／復号において符号帳の切り替え規則（つまり、次に使用する符号帳を決定する規則）は対応しており、符号化手順と復号手順との間で符号帳の切り替え規則が共有されていることがわかる。
　次に、第１実施形態における復号手順、すなわち、並列処理として実行する場合における復号手順を示す。Mを並列処理の単位を表す所定の整数（ただし、Mは2以上の整数）とする。また、w0w1 … wL-1（ただし、wi(i=0, …, L-1)は２つの符号帳T0, T1に含まれる符号語の長さと同じ長さの符号語）を入力符号語とする。このとき、並列処理として実行する場合における復号手順は以下の４つの処理からなる（図６参照）。
（１）入力符号語w0w1 ... wL-1を現在の符号語とする。開始符号帳であるT0を現在の符号帳とする。カウンタiを初期化する。つまり、i=0とする。
（２）符号語wi+j(j=0, ..., M-1)に対して以下の処理を並列に実行する。
（２－１）符号帳Tk(k=0, 1)を用いて、符号語wi+jと当該符号帳Tkに含まれる符号語を比較し、符号語wi+jに対応する記号列を候補記号列σ(j, k)として得る。また、候補記号列σ(j, k)を語頭とする記号列（ただし、当該記号列は候補記号列σ(j, k)と異なる）が、符号帳Tkに含まれる記号列の集合に含まれない場合はT0を次に使用する符号帳として得て、当該集合に含まれる場合はT1を次に使用する符号帳として得て、当該次に使用する符号帳を次に使用する候補符号帳Tn(j, k)とする。
（３）符号語wi+j(j=0, ..., M-1)に対して以下の処理を実行する。
（３－１）カウンタjを初期化する。つまり、j=0とする。
（３－２）現在の符号帳が符号帳Tk(kは0, 1のいずれか)である場合は、候補記号列σ(j, k)を符号語wi+jに対応する記号列として選択して得て、次に使用する候補符号帳Tn(j, k)を次に使用する符号帳として選択して得て、当該次に使用する符号帳を現在の符号帳とする。
（３－３）j<M-1である場合は、カウンタjを1インクリメント、つまり、j=j+1とし、（３－２）の処理に戻る一方で、それ以外の場合は、現在の符号語から符号語wi ... wi+M-1と一致した語頭を除いた符号語を現在の符号語とし、（４）の処理に進む。
（４）i<L-Mである場合は、カウンタiをMインクリメント、つまり、i=i+Mとし、（２）の処理に戻る一方で、それ以外の場合は（３－２）の処理により得られたすべての記号列を連結して得られる記号列を出力記号列として出力し復号処理を終了する。
　また、並列処理として実行する場合における復号手順は以下の４つの処理からなるともいえる。
（１）入力符号語を現在の符号語とする。開始符号帳であるT0を現在の符号帳とする。
（２）現在の符号語の先頭から２つの符号帳T0, T1に含まれる符号語の長さと同じ長さの符号語をM個取得する。取得したM個の符号語をw0, …, wM-1とする。符号語wj(j=0, …, M-1)に対して以下の処理を並列に実行する。
（２－１）符号帳Tk(k=0, 1)を用いて、符号語wjと当該符号帳Tkに含まれる符号語を比較し、符号語wjに対応する記号列を候補記号列σ(j, k)として得る。また、候補記号列σ(j, k)を語頭とする記号列（ただし、当該記号列は記号列σ(j, k)と異なる）が、符号帳Tkに含まれる記号列の集合に含まれない場合はT0を次に使用する符号帳として得て、当該集合に含まれる場合はT1を次に使用する符号帳として得て、当該次に使用する符号帳を次に使用する候補符号帳Tn(j, k)とする。
（３）符号語wj(j=0, …, M-1)に対して以下の処理を実行する。
（３－１）カウンタjを初期化する。
（３－２）現在の符号帳が符号帳Tk(kは0, 1のいずれか)である場合は、候補記号列σ(j, k)を符号語wjに対応する記号列として選択して得て、次に使用する候補符号帳Tn(j, k)を次に使用する符号帳として選択して得て、当該次に使用する符号帳を現在の符号帳とする。
（３－３）j<M-1である場合は、カウンタjを1インクリメントし、（３－２）の処理に戻る一方で、それ以外の場合は、現在の符号語から符号語w0 ... wM-1と一致した語頭を除いた符号語を現在の符号語とし、（４）の処理に進む。
（４）現在の符号語の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は（３－２）の処理により得られたすべての記号列を連結して得られる記号列を出力記号列として出力し復号処理を終了する。
　ここで、（２）の処理と（３－２）の処理からわかるように、並列処理として実行する場合における復号手順においても符号帳の切り替え規則に基づいて次に使用する符号帳が決められている。
＜＜３：復号の例＞＞
　ここでは、復号の例として、図５の符号帳を用いた場合における並列処理の単位Mが3であるときの符号語001101000に対する復号について説明する。開始符号帳を符号帳T0とする。入力符号語は符号語001101000であり、符号語001101000を現在の符号語とする。カウンタiを初期化する。なお、符号帳T0, T1に含まれる符号語の長さは3であることに留意する。
（１）符号語w0=001, w1=101, w2=000として、符号語w0, w1, w2に対して以下の処理を並列に実行する。
（符号語w0=001に対する処理）
（α）符号帳T0を用いて、符号語w0に対応する記号列aaを候補記号列σ(0, 0)として得る。また、候補記号列σ(0, 0)=aaを語頭とする（記号列aaとは異なる）記号列aaaが符号帳T0に含まれるので、符号帳T1を次に使用する候補符号帳Tn(0, 0)として得る。
（β）符号帳T1を用いて、符号語w0に対応する記号列baaを候補記号列σ(0, 1)として得る。また、候補記号列σ(0, 1)=baaを語頭とする（記号列baaとは異なる）記号列baaaが符号帳T1に含まれるので、符号帳T1を次に使用する候補符号帳Tn(0, 1)として得る。
（符号語w1=101に対する処理）
（α）符号帳T0を用いて、符号語w1に対応する記号列bを候補記号列σ(1, 0)として得る。また、候補記号列σ(1, 0)=bを語頭とする（記号列bとは異なる）記号列baが符号帳T0に含まれるので、符号帳T1を次に使用する候補符号帳Tn(1, 0)として得る。
（β）符号帳T1を用いて、符号語w1に対応する記号列bcを候補記号列σ(1, 1)として得る。また、候補記号列σ(1, 1)=bcを語頭とする記号列は符号帳T1には記号列bcしかないので、符号帳T0を次に使用する候補符号帳Tn(1, 1)として得る。
（符号語w2=000に対する処理）
（α）符号帳T0を用いて、符号語w2に対応する記号列aaaを候補記号列σ(2, 0)として得る。また、候補記号列σ(2, 0)=aaaを語頭とする記号列は符号帳T0には記号列aaaしかないので、符号帳T0を次に使用する候補符号帳Tn(2, 0)として得る。
（β）符号帳T1を用いて、符号語w2に対応する記号列baaaを候補記号列σ(2, 1)として得る。また、候補記号列σ(2, 1)=baaaを語頭とする記号列は符号帳T1には記号列baaaしかないので、符号帳T0を次に使用する候補符号帳Tn(2, 1)として得る。
（２）カウンタjを初期化し、符号語w0, w1, w2に対して以下の処理を実行する。
　現在の符号帳は符号帳T0であるので、候補記号列σ(0, 0)=aaを符号語w0に対応する記号列として選択し、次に使用する候補符号帳Tn(0, 0)=T1を現在の符号帳とする。また、j(=0)<M-1(=2)であるので、カウンタjを1インクリメントし、j=1とする。
　現在の符号帳は符号帳T1であるので、候補記号列σ(1, 1)=bcを符号語w1に対応する記号列として選択し、次に使用する候補符号帳Tn(1, 1)=T0を現在の符号帳とする。また、j(=1)<M-1(=2)であるので、カウンタjを1インクリメントし、j=2とする。
　現在の符号帳は符号帳T0であるので、候補記号列σ(2, 0)=aaaを符号語w2に対応する記号列として選択し、次に使用する候補符号帳Tn(2, 0)=T0を現在の符号帳とする。また、j(=2)≧M-1(=2)であり、かつ、i(=0)≧L-M(=0)であるので、選択された候補記号列σ(0, 0)=aa, σ(1, 1)=bc, σ(2, 0)=aaaを連結して得られる記号列aabcaaaを出力し復号処理を終了する。
＜第１実施形態＞
　本実施形態における符号化装置１００は、符号化対象となる記号列（以下、入力記号列という）を入力とし、当該入力記号列に対応する符号語（以下、出力符号語という）を出力する。また、本実施形態における復号装置２００は、復号対象となる符号語（以下、入力符号語という）を入力とし、当該入力符号語に対応する記号列（以下、出力記号列という）を出力する。
　ここで、符号語とは、2つの符号{0, 1}を一列にならべてできる列のことである。また、記号とは、有限個の要素からなる集合の要素のことであり、例えばアルファベットの集合{a, b, c }の要素であるa, b, cのようなアルファベットや単語で構成されるテキストでよい。記号列とは、記号を一列にならべてできる列のことであり、例えば、2つの記号{a, b}に対してabbaaは長さが5である記号列である。
　記号列として、例えば量子化されるなどして有限精度の数値となっている以下の系列が例示できる。
（１）音声信号、画像信号、輝度センサや加速度センサや地震計などの各種センサから得られた時系列信号
（２）（１）の信号の離散フーリエ変換、離散コサイン変換、修正離散コサイン変換などにより得られるスペクトル値の系列
（３）（１）の信号を線形予測分析して得られる線形予測係数、線スペクトル対（LSP）、イミタンススペクトルペア（ISP）、偏自己相関係数（PARCOR係数）の系列
（４）（１）の信号をニューラルネットワークに入力して得られる特徴量の系列
　つまり、記号列は有限精度のディジタル信号の系列やディジタルデータの系列である。
　また、並列処理には、並列処理の対象となる複数の処理すべてを同じタイミングで実行する処理形態だけでなく、ある処理が別の処理の終了前に開始される形で複数の処理が実行される処理形態も含むものとする。
　符号化装置１００や復号装置２００が符号化処理や復号処理で用いる２つの符号帳または解析木T0, T1は以下の特徴を備えるデータ構造である。
（１）２つの符号帳または解析木T0, T1は、非特許文献１の技術に従い構成された符号帳または解析木であり、記号列と所定の長さの符号語の２つ組から構成される。
　したがって、２つの符号帳または解析木T0, T1に含まれる符号語はすべて長さが同じである。
　上述した通り、図５の符号帳が符号帳T0, T1の一例であり、図２(A)の解析木が解析木T0, T1の一例である。
＜＜符号化装置１００＞＞
　以下、図７～図８を参照して符号化装置１００を説明する。図７は、符号化装置１００の構成を示すブロック図である。図８は、符号化装置１００の動作を示すフローチャートである。図７に示すように符号化装置１００は、符号化部１１０と、記録部１９０を含む。記録部１９０は、符号化装置１００の処理に必要な情報を適宜記録する構成部である。記録部１９０は、例えば２つの符号帳または解析木T0, T1を記録しておく。
　図８に従い符号化装置１００の動作について説明する。
　Ｓ１１０において、符号化部１１０は、２つの符号帳または解析木T0, T1を用いて入力記号列を構成する記号列に対応する符号語を得て、得られた符号語を連結して得られる符号語を出力符号語として出力する。
　符号化部１１０は、以下の３つの処理からなる符号化処理を実行する。
（１）入力記号列を現在の記号列とし、開始符号帳または開始解析木を現在の符号帳または解析木とする処理
（２）現在の符号帳または解析木を用いて、現在の記号列と当該符号帳または解析木に含まれる記号列を比較し、現在の記号列の語頭と最も長く一致する、現在の符号帳または解析木に含まれる記号列σに対応する符号語を得て、現在の記号列から当該記号列σと一致した語頭を除いた記号列を現在の記号列とし、記号列σを語頭とする記号列（ただし、当該記号列は記号列σと異なる）が、現在の符号帳または解析木に含まれる記号列の集合に含まれない場合はT0を次に使用する符号帳または解析木として得て、当該集合に含まれる場合はT1を次に使用する符号帳または解析木として得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
（３）現在の記号列の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は（２）の処理により得られたすべての符号語を連結して得られる符号語を出力符号語として出力し符号化処理を終了する処理
＜＜復号装置２００＞＞
　以下、図９～図１０を参照して復号装置２００を説明する。図９は、復号装置２００の構成を示すブロック図である。図１０は、復号装置２００の動作を示すフローチャートである。図９に示すように復号装置２００は、復号部２１０と、記録部２９０を含む。記録部２９０は、復号装置２００の処理に必要な情報を適宜記録する構成部である。記録部２９０は、例えば２つの符号帳または解析木T0, T1（ただし、符号帳または解析木T0, T1は入力符号語を得るための符号化処理で用いた符号帳または解析木と同一である）を記録しておく。また、記録部２９０は、例えば開始符号帳または開始解析木に関する情報を記録しておく。
　図１０に従い復号装置２００の動作について説明する。ここで、Mを並列処理の単位を表す所定の整数（ただし、Mは2以上の整数）とする。
　Ｓ２１０において、復号部２１０は、２つの符号帳または解析木T0, T1を用いて入力符号語を構成する符号語に対応する記号列を得て、得られた記号列を連結して得られる記号列を出力記号列として出力する。
　復号部２１０は、以下の４つの処理からなる復号処理を実行する。
（１）入力符号語を現在の符号語とし、開始符号帳または開始解析木を現在の符号帳または解析木とする処理
（２）現在の符号語の先頭から２つの符号帳または解析木T0, T1に含まれる符号語の長さと同じ長さの符号語をM個取得し、当該M個の符号語wj(j=0, …, M-1)に対して（２－１）の処理を並列に実行する処理
（２－１）符号帳または解析木Tk(k=0, 1)を用いて、符号語wjと当該符号帳Tkに含まれる符号語を比較し、符号語wjに対応する記号列を候補記号列σ(j, k)として得て、候補記号列σ(j, k)を語頭とする記号列（ただし、当該記号列は候補記号列σ(j, k)と異なる）が、符号帳または解析木Tkに含まれる記号列の集合に含まれない場合はT0を次に使用する符号帳または解析木として得て、当該集合に含まれる場合はT1を次に使用する符号帳または解析木として得て、当該次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木Tn(j, k)とする処理
（３）符号語wj(j=0, …, M-1)に対して（３－１）～（３－３）の処理を実行する処理
（３－１）カウンタjを初期化する処理
（３－２）現在の符号帳または解析木が符号帳または解析木Tk(kは0, 1のいずれか)である場合は、候補記号列σ(j, k)を符号語wjに対応する記号列として選択して得て、次に使用する候補符号帳または候補解析木Tn(j, k)を次に使用する符号帳または解析木として選択して得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
（３－３）j<M-1である場合は、カウンタjを1インクリメントし、（３－２）の処理に戻る一方で、それ以外の場合は、現在の符号語から符号語w0 ... wM-1と一致した語頭を除いた符号語を現在の符号語とし、（４）の処理に進む処理
（４）現在の符号語の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は（３－２）の処理により得られたすべての記号列を連結して得られる記号列を出力記号列として出力し復号処理を終了する処理
　本発明の実施形態によれば、複数の符号帳または解析木を用いた復号処理にかかる時間を短縮することが可能となる。より詳しくは、複数の符号語に対して当該符号語に対応する記号列の候補と次に使用する符号帳または解析木の候補を取得する処理を並列に実行することにより、符号語に対応する記号列や次に使用する符号帳または解析木を取得するために必要となる処理時間を短縮しながら、複数の符号帳または解析木を用いた復号処理を実行することが可能となる。上記並列処理の効果は、符号帳または解析木のサイズが大きく、記号列の取得に処理時間を要する場合に特に大きいものとなる。
＜技術的背景＞
　第１実施形態における符号化／復号では、一意符号化可能性条件を満たす符号化規則を表現することができる非特許文献１の技術に基づく符号帳を用いた。ここでは、第１実施形態とは異なる、一意符号化可能性条件を満たす符号化規則を表現することができる複数の符号帳を用いる実施形態について説明する。なお、符号帳の代わりに解析木を用いてもよく、符号化手順／復号手順に違いが生じることはない。
＜＜１：符号帳＞＞
　ここでは、第２実施形態における符号帳について説明する。
　まず、第２実施形態における符号帳の説明に必要となる概念である記号列モードについて説明する。符号帳に対して記号列の集合を記号列モードと定義する。符号化／復号に用いる複数の符号帳それぞれに対して記号列モードが割り当てられる。符号帳に割り当てられる記号列モードは記号列の集合として定義するため、記号列モードに含まれる記号列の重複はないものとする。なお、記号列モードは語頭条件を満たしていることが好ましい。ここで、語頭条件とは、記号列を要素とする集合に含まれる任意の記号列に対して当該記号列が当該集合に含まれる他の記号列の語頭にならないという条件である。
　第２実施形態における符号帳は、入力となる記号列と出力となる所定の長さの符号語と次に使用する符号帳（以下、リンク先という）の３つ組から構成される。図１１は符号帳の例を示す図である。図１１の符号帳は記号{a, b, c}の列である記号列を符号{0, 1}の列である符号語に符号化するために用いるものであり、T0, T1, T2, T3, T4の５つの符号帳からなる。符号帳T0, T1, T2, T3, T4に含まれる符号語の長さは2であることに留意する。例えば、符号帳T0には記号列モード{ε}が、符号帳T1には記号列モード{a, b}が割り当てられている。また、符号帳T0は記号列aに対して符号語00を出力し次に使用する符号帳をT1とし、記号列εに対して符号語01を出力し次に使用する符号帳をT2とすることを表している。
　次に、第２実施形態における符号化／復号が一意符号化可能性条件を満たすために、符号帳に求められる条件について説明する。そのために、展開記号列という概念を定義する。記号列が符号帳の展開記号列であるとは、当該符号帳に含まれる記号列と当該記号列に対応する次に使用する符号帳に割り当てられた記号列モードの要素である記号列とを連結させて得られる記号列である。例えば、図１１の符号帳T2の展開記号列は、記号列acaと記号列acaに対応する次に使用する符号帳T0に割り当てられた記号列モード{ε}の要素である記号列εとを連結させて得られる記号列aca、記号列baaと記号列baaに対応する次に使用する符号帳T0に割り当てられた記号列モード{ε}の要素である記号列εとを連結させて得られる記号列baa、記号列acと記号列acに対応する次に使用する符号帳T3に割り当てられた記号列モード{b, c}の要素である記号列bやcとを連結させて得られる記号列acbやacc、記号列baと記号列baに対応する次に使用する符号帳T3に割り当てられた記号列モード{b, c}の要素である記号列bやcとを連結させて得られる記号列babやbacのことである。
　符号化／復号が一意符号化可能性条件を満たすために符号帳に求められる条件は、以下の２つの条件である。
（１）複数の符号帳に含まれる任意の符号帳に対して、当該符号帳のすべての展開記号列からなる集合は語頭条件を満たす。
（２）複数の符号帳に含まれる任意の符号帳に対して、当該符号帳の展開記号列は当該符号帳に割り当てられた記号列モードに含まれるいずれかの記号列を語頭とする。
　なお、符号化／復号に用いる複数の符号帳が一意符号化可能性条件を満たしていなくても、当該複数の符号帳を用いて符号化された符号語は一意に記号列に復号することができる。しかし、圧縮効率の観点からは、符号化／復号に用いる複数の符号帳は一意符号化可能性条件を満たしていることが好ましい。
　また、上述した通り、符号化規則は解析木を用いて表現することもできる。図１２は解析木の例を示す図であり、図１２の解析木は図１１の符号帳と等価である。上記符号帳に関する説明は、符号帳とある個所を解析木と読み替えるだけで解析木についても妥当する。読み替えにより、以下のような解析木に関する説明が得られる。
　解析木に対して記号列の集合を記号列モードと定義する。符号化／復号に用いる複数の解析木それぞれに対して記号列モードが割り当てられる。
　解析木は、入力となる記号列と出力となる所定の長さの符号語と次に使用する解析木（以下、リンク先という）の３つ組から構成される。
　記号列が解析木の展開記号列であるとは、当該解析木に含まれる記号列と当該記号列に対応する次に使用する解析木に割り当てられた記号列モードの要素である記号列とを連結させて得られる記号列である。
　符号化／復号が一意符号化可能性条件を満たすために解析木に求められる条件は、以下の２つの条件である。
（１）複数の解析木に含まれる任意の解析木に対して、当該解析木のすべての展開記号列からなる集合は語頭条件を満たす。
（２）複数の解析木に含まれる任意の解析木に対して、当該解析木の展開記号列は当該解析木に割り当てられた記号列モードに含まれるいずれかの記号列を語頭とする。
　なお、第２実施形態の方が第１実施形態より多くの符号帳を用いることができるため、第２実施形態の方が圧縮効率がよいものとなる。
＜＜２：符号化手順／復号手順＞＞
　第２実施形態における符号化手順は、符号化対象となる記号列（以下、入力記号列という）を入力とし、複数の符号帳{Tk}k=0 K-1（ただし、Kは2以上の整数）を用いて入力記号列を構成する記号列に対応する符号語を得て、得られたすべての符号語を連結して得られる符号語（以下、出力符号語という）を出力する。また、第２実施形態における復号手順は、復号対象となる符号語（以下、入力符号語という）を入力とし、複数の符号帳{Tk}k=0 K-1（ただし、符号帳{Tk}k=0 K-1は符号化手順で用いた符号帳）を用いて入力符号語を構成する符号語に対応する記号列を得て、得られたすべての記号列を連結して得られる記号列（以下、出力記号列という）を出力する。
　なお、符号化を開始する際に用いる符号帳（以下、開始符号帳という）は任意であるが、どの符号帳を用いて符号化を開始したのかという開始符号帳に関する情報は、符号化手順と復号手順の間で共有される。
（符号化手順）
　現在の記号列を現時点において符号化処理の対象である記号列、現在の符号帳を現時点において符号化処理に用いるべき符号帳とする。したがって、符号化を開始した時点における現在の記号列、現在の符号帳はそれぞれ入力記号列、開始符号帳である。
　第２実施形態における符号化手順は以下の３つの処理からなる。
（１）入力記号列を現在の記号列とする。また、開始符号帳を現在の符号帳とする。
（２）現在の符号帳を用いて、現在の記号列と当該符号帳に含まれる記号列を比較する。現在の記号列の語頭と一致する、現在の符号帳に含まれる記号列σが存在し、かつ、現在の記号列から当該記号列σと一致した語頭を除いた記号列の語頭と一致する、当該記号列σに対応する次に使用する符号帳に割り当てられた記号列モードに含まれる記号列が存在する場合は、当該記号列σに対応する符号語を得て、現在の記号列から当該記号列σと一致した語頭を除いた記号列を現在の記号列とする。また、記号列σに対応する次に使用する符号帳を現在の符号帳とする。
（３）現在の記号列の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は（２）の処理により得られたすべての符号語を連結して得られる符号語を出力符号語として出力し符号化処理を終了する。
（復号手順）
　現在の符号語を現時点において復号処理の対象である符号語、現在の符号帳を現時点において復号処理に用いるべき符号帳とする。したがって、復号を開始した時点における現在の符号語、現在の符号帳はそれぞれ入力符号語、開始符号帳である。
　まず、並列処理として実行しない場合における復号手順を示す。当該復号手順は以下の３つの処理からなる。
（１）入力符号語を現在の符号語とする。また、開始符号帳を現在の符号帳とする。
（２）現在の符号帳を用いて、現在の符号語と当該符号帳に含まれる符号語を比較する。現在の符号語の語頭と一致する、現在の符号帳に含まれる符号語wに対応する記号列を得て、現在の符号語から当該符号語wと一致した語頭を除いた符号語を現在の符号語とする。符号語wに対応する次に使用する符号帳を現在の符号帳とする。
（３）現在の符号語の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は（２）の処理により得られたすべての記号列を連結して得られる記号列を出力記号列として出力し復号処理を終了する。
　ここで、符号化手順における（２）の処理と復号手順における（２）の処理とを比較すると、符号化／復号において符号帳の切り替え規則（つまり、次に使用する符号帳を決定する規則）は対応しており、符号化手順と復号手順において同じ複数の符号帳{Tk}k=0 K-1が用いられることにより、符号化手順と復号手順との間で符号帳の切り替え規則が共有されていることがわかる。
　次に、第２実施形態における復号手順、すなわち、並列処理として実行する場合における復号手順を示す。Mを並列処理の単位を表す所定の整数（ただし、Mは2以上の整数）とする。また、w0w1 … wL-1（ただし、wi(i=0, …, L-1)は複数の符号帳{Tk}k=0 K-1に含まれる符号語の長さと同じ長さの符号語）を入力符号語とする。このとき、並列処理として実行する場合における復号手順は以下の４つの処理からなる（図６参照）。
（１）入力符号語w0w1 ... wL-1を現在の符号語とする。開始符号帳を現在の符号帳とする。カウンタiを初期化する。つまり、i=0とする。
（２）符号語wi+j(j=0, ..., M-1)に対して以下の処理を並列に実行する。
（２－１）符号帳Tk(k=0, ..., K-1)を用いて、符号語wi+jと当該符号帳Tkに含まれる符号語を比較し、符号語wi+jに対応する記号列を候補記号列σ(j, k)として得る。また、符号語wi+jに対応する次に使用する符号帳を次に使用する候補符号帳Tn(j, k)として得る。
（３）符号語wi+j(j=0, ..., M-1)に対して以下の処理を実行する。
（３－１）カウンタjを初期化する。つまり、j=0とする。
（３－２）現在の符号帳が符号帳Tk(kは0, ..., K-1のいずれか)である場合は、候補記号列σ(j, k)を符号語wi+jに対応する記号列として選択して得て、次に使用する候補符号帳Tn(j, k)を次に使用する符号帳として選択して得て、当該次に使用する符号帳を現在の符号帳とする。
（３－３）j<M-1である場合は、カウンタjを1インクリメント、つまり、j=j+1とし、（３－２）の処理に戻る一方で、それ以外の場合は、現在の符号語から符号語wi ... wi+M-1と一致した語頭を除いた符号語を現在の符号語とし、（４）の処理に進む。
（４）i<L-Mである場合は、カウンタiをMインクリメント、つまり、i=i+Mとし、（２）の処理に戻る一方で、それ以外の場合は（３－２）の処理により得られたすべての記号列を連結して得られる記号列を出力記号列として出力し復号処理を終了する。
　また、並列処理として実行する場合における復号手順は以下の４つの処理からなるともいえる。
（１）入力符号語を現在の符号語とする。開始符号帳を現在の符号帳とする。
（２）現在の符号語の先頭から複数の符号帳{Tk}k=0 K-1に含まれる符号語の長さと同じ長さの符号語をM個取得する。取得したM個の符号語をw0, …, wM-1とする。符号語wj(j=0, …, M-1)に対して以下の処理を並列に実行する。
（２－１）符号帳Tk(k=0, ..., K-1)を用いて、符号語wjと当該符号帳Tkに含まれる符号語を比較し、符号語wjに対応する記号列を候補記号列σ(j, k)として得る。また、符号語wjに対応する次に使用する符号帳を次に使用する候補符号帳Tn(j, k)として得る。
（３）符号語wj(j=0, …, M-1)に対して以下の処理を実行する。
（３－１）カウンタjを初期化する。
（３－２）現在の符号帳が符号帳Tk(kは0, ..., K-1のいずれか)である場合は、候補記号列σ(j, k)を符号語wjに対応する記号列として選択して得て、次に使用する候補符号帳Tn(j, k)を次に使用する符号帳として選択して得て、当該次に使用する符号帳を現在の符号帳とする。
（３－３）j<M-1である場合は、カウンタjを1インクリメントし、（３－２）の処理に戻る一方で、それ以外の場合は、現在の符号語から符号語w0 ... wM-1と一致した語頭を除いた符号語を現在の符号語とし、（４）の処理に進む。
（４）現在の符号語の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は（３－２）の処理により得られたすべての記号列を連結して得られる記号列を出力記号列として出力し復号処理を終了する。
　ここで、（２）の処理と（３－２）の処理からわかるように、並列処理として実行する場合における復号手順においても符号帳の切り替え規則に基づいて次に使用する符号帳が決められている。
＜第２実施形態＞
　本実施形態における符号化装置１００は、符号化対象となる記号列（以下、入力記号列という）を入力とし、当該入力記号列に対応する符号語（以下、出力符号語という）を出力する。また、本実施形態における復号装置２００は、復号対象となる符号語（以下、入力符号語という）を入力とし、当該入力符号語に対応する記号列（以下、出力記号列という）を出力する。
　符号化装置１００や復号装置２００が符号化処理や復号処理で用いる複数の符号帳または解析木{Tk}k=0 K-1（ただし、Kは2以上の整数）は以下の特徴を備えるデータ構造である。
（１）符号帳または解析木Tk(k=0, 1 ,…, K-1)は、記号列と所定の長さの符号語と次に使用する符号帳または解析木の３つ組から構成され、記号列の集合である記号列モードが割り当てられたものである。したがって、符号帳または解析木Tk(k=0, 1 ,…, K-1)に含まれる符号語はすべて長さが同じである。
（２）符号帳または解析木Tk(k=0, 1 ,…, K-1)のすべての展開記号列からなる集合は語頭条件を満たすという条件と、符号帳または解析木Tk(k=0, 1 ,…, K-1)の展開記号列は当該符号帳または解析木Tkに割り当てられた記号列モードに含まれるいずれかの記号列を語頭とするという条件を満たすものである。
　上述した通り、複数の符号帳または解析木{Tk}k=0 K-1が条件（１）及び条件（２）を満たす場合、複数の符号帳または解析木{Tk}k=0 K-1は一意符号化可能性条件を満たす。ただし、複数の符号帳または解析木{Tk}k=0 K-1は条件（２）を満たすだけで符号としては十分である。
＜＜符号化装置１００＞＞
　以下、図７～図８を参照して符号化装置１００を説明する。図７は、符号化装置１００の構成を示すブロック図である。図８は、符号化装置１００の動作を示すフローチャートである。図７に示すように符号化装置１００は、符号化部１１０と、記録部１９０を含む。記録部１９０は、符号化装置１００の処理に必要な情報を適宜記録する構成部である。記録部１９０は、例えば複数の符号帳または解析木{Tk}k=0 K-1を記録しておく。
　図８に従い符号化装置１００の動作について説明する。
　Ｓ１１０において、符号化部１１０は、複数の符号帳または解析木{Tk}k=0 K-1を用いて入力記号列を構成する記号列に対応する符号語を得て、得られた符号語を連結して得られる符号語を出力符号語として出力する。
　符号化部１１０は、以下の３つの処理からなる符号化処理を実行する。
（１）入力記号列を現在の記号列とし、開始符号帳または開始解析木を現在の符号帳または解析木とする処理
（２）現在の符号帳または解析木を用いて、現在の記号列と当該符号帳または解析木に含まれる記号列を比較し、現在の記号列の語頭と一致する、現在の符号帳または解析木に含まれる記号列σが存在し、かつ、現在の記号列から当該記号列σと一致した語頭を除いた記号列の語頭と一致する、当該記号列σに対応する次に使用する符号帳または解析木に割り当てられた記号列モードに含まれる記号列が存在する場合は、当該記号列σに対応する符号語を得て、現在の記号列から当該記号列σと一致した語頭を除いた記号列を現在の記号列とし、記号列σに対応する次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
（３）現在の記号列の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は（２）の処理により得られたすべての符号語を連結して得られる符号語を出力符号語として出力し符号化処理を終了する処理
＜＜復号装置２００＞＞
　以下、図９～図１０を参照して復号装置２００を説明する。図９は、復号装置２００の構成を示すブロック図である。図１０は、復号装置２００の動作を示すフローチャートである。図９に示すように復号装置２００は、復号部２１０と、記録部２９０を含む。記録部２９０は、復号装置２００の処理に必要な情報を適宜記録する構成部である。記録部２９０は、例えば複数の符号帳または解析木{Tk}k=0 K-1（ただし、符号帳{Tk}k=0 K-1は入力符号語を得るための符号化処理で用いた符号帳または解析木と同一である）を記録しておく。
　図１０に従い復号装置２００の動作について説明する。ここで、Mを並列処理の単位を表す所定の整数（ただし、Mは2以上の整数）とする。
　Ｓ２１０において、復号部２１０は、複数の符号帳または解析木{Tk}k=0 K-1を用いて入力符号語を構成する符号語に対応する記号列を得て、得られた記号列を連結して得られる記号列を出力記号列として出力する。
　復号部２１０は、以下の４つの処理からなる復号処理を実行する。
（１）入力符号語を現在の符号語とし、開始符号帳または開始解析木を現在の符号帳または解析木とする処理
（２）現在の符号語の先頭から複数の符号帳または解析木{Tk}k=0 K-1に含まれる符号語の長さと同じ長さの符号語をM個取得し、当該取得したM個の符号語wj(j=0, …, M-1)に対して（２－１）の処理を並列に実行する処理
（２－１）符号帳または解析木Tk(k=0, ..., K-1)を用いて、符号語wjと当該符号帳または解析木Tkに含まれる符号語を比較し、符号語wjに対応する記号列を候補記号列σ(j, k)として得て、符号語wjに対応する次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木Tn(j, k)として得る処理
（３）符号語wj(j=0, …, M-1)に対して（３－１）～（３－３）の処理を実行する処理
（３－１）カウンタjを初期化する処理
（３－２）現在の符号帳または解析木が符号帳または解析木Tk(kは0, ..., K-1のいずれか)である場合は、候補記号列σ(j, k)を符号語wjに対応する記号列として選択して得て、次に使用する候補符号帳または候補解析木Tn(j, k)を次に使用する符号帳または解析木として選択して得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
（３－３）j<M-1である場合は、カウンタjを1インクリメントし、（３－２）の処理に戻る一方で、それ以外の場合は、現在の符号語から符号語w0 ... wM-1と一致した語頭を除いた符号語を現在の符号語とし、（４）の処理に進む処理
（４）現在の符号語の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は（３－２）の処理により得られたすべての記号列を連結して得られる記号列を出力記号列として出力し復号処理を終了する処理
＜＜変形例＞＞
　復号処理においてすべての符号帳または解析木に対して（２）の処理を実行すると、処理が重くなることがある。そこで、例えば、想定される記号列の出現に関する確率分布に基づいてどの符号帳に切り替わりやすいかという確率を予め求め、当該確率が高い符号帳についてのみ（２）の処理を実行するようにするなど、必ずしもすべての符号帳に対して（２）の処理を実行することがないようにしてもよい。この場合、（３－２）の処理において符号語に対応する記号列が取得できていないときには、その都度符号語に対応する記号列を取得するようにすればよい。
　（３－２）の処理において符号語に対応する記号列が取得できていない頻度が小さい場合には、回路（例えば、CPU、GPU、FPGA）やメモリなどの計算資源を節約しながら処理速度を向上させることが可能となる。
　復号部２１０は、Ｓ２１０において以下の４つの処理からなる復号処理を実行することとなる。
（１）入力符号語を現在の符号語とし、開始符号帳または開始解析木を現在の符号帳または解析木とする処理
（２）現在の符号語の先頭から複数の符号帳または解析木{Tk}k=0 K-1に含まれる符号語の長さと同じ長さの符号語をM個取得し、当該取得したM個の符号語wj(j=0, …, M-1)に対して（２－１）の処理を並列に実行する処理
（２－１）符号帳または解析木Tk(k=k(0), ..., k(N-1)、ただし、Nは1以上K-1以下の整数、k(0), ..., k(N-1)は互いに異なる0以上K-1以下の整数)を用いて、符号語wjと当該符号帳または解析木Tkに含まれる符号語を比較し、符号語wjに対応する記号列を候補記号列σ(j, k)として得て、符号語wjに対応する次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木Tn(j, k)として得る処理
（３）符号語wj(j=0, …, M-1)に対して（３－１）～（３－３）の処理を実行する処理
（３－１）カウンタjを初期化する処理
（３－２）現在の符号帳または解析木が符号帳または解析木Tk(kはk(0), ..., k(N-1)のいずれか)である場合は、候補記号列σ(j, k)を符号語wjに対応する記号列として選択して得て、次に使用する候補符号帳または候補解析木Tn(j, k)を次に使用する符号帳または解析木として選択して得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とし、それ以外の場合は、符号帳または解析木Tk(kはk(0), ..., k(N-1)のいずれでもない)を用いて、符号語wjと当該符号帳または解析木Tkに含まれる符号語を比較し、符号語wjに対応する記号列を得て、符号語wjに対応する次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
（３－３）j<M-1である場合は、カウンタjを1インクリメントし、（３－２）の処理に戻る一方で、それ以外の場合は、現在の符号語から符号語w0 ... wM-1と一致した語頭を除いた符号語を現在の符号語とし、（４）の処理に進む処理
（４）現在の符号語の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は（３－２）の処理により得られたすべての記号列を連結して得られる記号列を出力記号列として出力し復号処理を終了する処理
　なお、（２）の処理で対象とする符号帳または解析木は、例えば、記号列の出現に関する確率分布に基づいて、使用される可能性が高いと判断される符号帳または解析木とするとよい。
　また、第１実施形態についても一部の符号帳または解析木を用いて候補記号列を得るようにしてもよい。この場合、（２－１）の処理、（３－２）の処理は以下のようになる。
（２－１）符号帳または解析木Tk(k=k(0)、ただし、k(0)は0以上1以下の整数)を用いて、符号語wjと当該符号帳または解析木Tkに含まれる符号語を比較し、符号語wjに対応する記号列を候補記号列σ(j, k)として得て、候補記号列σ(j, k)を語頭とする記号列（ただし、当該記号列は候補記号列σ(j, k)と異なる）が、符号帳または解析木Tkに含まれる記号列の集合に含まれない場合はT0を次に使用する符号帳または解析木として得て、当該集合に含まれる場合はT1を次に使用する符号帳または解析木として得て、当該次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木Tn(j, k)とする処理
（３－２）現在の符号帳または解析木が符号帳または解析木Tk(kはk(0)である)である場合は、候補記号列σ(j, k)を符号語wjに対応する記号列として選択して得て、次に使用する候補符号帳または候補解析木Tn(j, k)を次に使用する符号帳または解析木として選択して得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とし、それ以外の場合は、符号帳Tk(kはk(0)でない)を用いて、符号語wjと当該符号帳または解析木Tkに含まれる符号語を比較し、符号語wjに対応する記号列を得て、符号語wjに対応する記号列を語頭とする記号列（ただし、当該記号列は符号語wjに対応する記号列と異なる）が、符号帳または解析木Tkに含まれる記号列の集合に含まれない場合はT0を次に使用する符号帳または解析木として得て、当該集合に含まれる場合はT1を次に使用する符号帳または解析木として得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
　本発明の実施形態によれば、複数の符号帳または解析木を用いた復号処理にかかる時間を短縮することが可能となる。より詳しくは、複数の符号語に対して当該符号語に対応する記号列の候補と次に使用する符号帳または解析木の候補を取得する処理を並列に実行することにより、符号語に対応する記号列や次に使用する符号帳または解析木を取得するために必要となる処理時間を短縮しながら、複数の符号帳または解析木を用いた復号処理を実行することが可能となる。上記並列処理の効果は、符号帳または解析木のサイズが大きく、記号列の取得に処理時間を要する場合に特に大きいものとなる。
＜第１実施形態や第２実施形態における復号部２１０＞
　第１実施形態や第２実施形態における復号部２１０は、所定の符号帳または解析木の切り替え規則に基づいて複数の符号帳または解析木を用いて復号処理を実行している。詳しくは、復号部２１０は、以下の２つの処理から構成される処理を繰り返し実行するものであるといえる。
（１）入力符号語を構成する複数の符号語に対して、
　複数の符号帳または解析木に含まれる１以上の所定の符号帳または解析木を用いて符号語に対応する記号列を候補記号列として得て、符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木として得る処理
　を並列に実行する処理
（２）入力符号語を構成する複数の符号語に対して、
　符号語に対して得られた候補記号列と次に使用する候補符号帳または候補解析木の組と、現在の符号帳または解析木と、符号帳または解析木の切り替え規則とに基づいて、当該符号語に対応する記号列と次に使用する符号帳または解析木の組を得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
　を逐次実行する処理
　さらに詳しくは、すべての複数の符号帳または解析木を用いる場合は、復号部２１０は、以下の処理を実行するものであるといえる。
（１）入力符号語を現在の符号語とし、開始符号帳または開始解析木（ただし、当該開始符号帳または開始解析木は複数の符号帳または解析木{Tk}k=0 K-1のいずれかである）を現在の符号帳または解析木とする処理
（２）現在の符号語の先頭から複数の符号帳または解析木{Tk}k=0 K-1に含まれる符号語の長さと同じ長さの符号語をM個取得し、当該取得したM個の符号語wj(j=0, …, M-1)に対して（２－１）の処理を並列に実行する処理
（２－１）符号帳または解析木Tk(k=0, ..., K-1)を用いて、符号語wjと当該符号帳または解析木Tkに含まれる符号語を比較し、符号語wjに対応する記号列を候補記号列σ(j, k)として得て、符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木Tn(j, k)として得る処理
（３）符号語wj(j=0, …, M-1)に対して（３－１）～（３－３）の処理を実行する処理
（３－１）カウンタjを初期化する処理
（３－２）現在の符号帳または解析木が符号帳または解析木Tk(kは0, ..., K-1のいずれか)である場合は、候補記号列σ(j, k)を符号語wjに対応する記号列として選択して得て、次に使用する候補符号帳または候補解析木Tn(j, k)を次に使用する符号帳または解析木として選択して得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
（３－３）j<M-1である場合は、カウンタjを1インクリメントし、（３－２）の処理に戻る一方で、それ以外の場合は、現在の符号語から符号語w0 ... wM-1と一致した語頭を除いた符号語を現在の符号語とし、（４）の処理に進む処理
（４）現在の符号語の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は（３－２）の処理により得られたすべての記号列を連結して得られる記号列を出力記号列として出力し復号処理を終了する処理
　また、一部の複数の符号帳または解析木を用いる場合は、復号部２１０は、以下の処理を実行するものであるといえる。
（１）入力符号語を現在の符号語とし、開始符号帳または開始解析木（ただし、当該開始符号帳または開始解析木は複数の符号帳または解析木{Tk}k=0 K-1のいずれかである）を現在の符号帳または解析木とする処理
（２）現在の符号語の先頭から複数の符号帳または解析木{Tk}k=0 K-1に含まれる符号語の長さと同じ長さの符号語をM個取得し、当該取得したM個の符号語wj(j=0, …, M-1)に対して（２－１）の処理を並列に実行する処理
（２－１）符号帳または解析木Tk(k=k(0), ..., k(N-1)、ただし、Nは1以上K-1以下の整数、k(0), ..., k(N-1)は互いに異なる0以上K-1以下の整数)を用いて、符号語wjと当該符号帳または解析木Tkに含まれる符号語を比較し、符号語wjに対応する記号列を候補記号列σ(j, k)として得て、符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木Tn(j, k)として得る処理
（３）符号語wj(j=0, …, M-1)に対して（３－１）～（３－３）の処理を実行する処理
（３－１）カウンタjを初期化する処理
（３－２）現在の符号帳または解析木が符号帳または解析木Tk(kはk(0), ..., k(N-1)のいずれか)である場合は、候補記号列σ(j, k)を符号語wjに対応する記号列として選択して得て、次に使用する候補符号帳または候補解析木Tn(j, k)を次に使用する符号帳または解析木として選択して得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とし、それ以外の場合は、符号帳または解析木Tk(kはk(0), ..., k(N-1)のいずれでもない)を用いて、符号語wjと当該符号帳または解析木Tkに含まれる符号語を比較し、符号語wjに対応する記号列を得て、符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
（３－３）j<M-1である場合は、カウンタjを1インクリメントし、（３－２）の処理に戻る一方で、それ以外の場合は、現在の符号語から符号語w0 ... wM-1と一致した語頭を除いた符号語を現在の符号語とし、（４）の処理に進む処理
（４）現在の符号語の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は（３－２）の処理により得られたすべての記号列を連結して得られる記号列を出力記号列として出力し復号処理を終了する処理
＜技術的背景＞
　第１実施形態や第２実施形態における復号処理では、出力記号列を得るために得られたすべての記号列を連結する処理を実行していた。しかし、得られた記号列を外部の記憶装置に書き出すことなく、内部の記憶装置であるメモリに残したままその後の処理を実行することもある。この場合、符号化処理と異なり、出力記号列を得るための連結処理を実行することなく、当該得られた記号列を取り扱うことができる。また、当該得られた記号列がメモリ上の連続した位置に記憶される必要はなく、当該記号列が記憶されるメモリ上の位置さえわかればその後の処理で出力記号列に相当する１つの記号列として利用することができる。
　図１３は復号処理におけるメモリの様子を示す図である。図１３(A)は、第１実施形態や第２実施形態の復号処理において並列に実行される（２）の処理結果を記憶するメモリ（以下、第１メモリという）の様子を示したものである。第１メモリは、復号対象である符号語を構成する符号語それぞれに対してK個の符号帳を用いて得られるK個の記号列を記憶する。図１３(B)は、第１実施形態や第２実施形態の復号処理において逐次実行される（３）の処理結果を記憶するメモリ（以下、第２メモリという）の様子を示したものである。第２メモリは、復号対象である符号語を構成する符号語に対応するK個の記号列のうち、選択された記号列の記憶領域の開始位置を示すアドレスと当該選択された記号列の長さの組を記憶する。図１３(B)は、例えば、復号対象となる符号語におけるi番目の区切りから始まる符号語wiに対応する記号列が、アドレスがAtである記憶領域に格納されており、当該記号列の長さが|σ(i,0)|であることを表している。したがって、符号語wiに対応する記号列σiにアクセスする場合、第２メモリにおいて記号列σiの記憶領域の開始位置を示す第１メモリにおけるアドレスと記号列σiの長さを参照し、第１メモリにおいて当該アドレスを用いて記号列σiの記憶領域の開始位置を特定し、記号列σiの長さを用いて記号列σiの記憶領域の範囲を特定し、記号列σiを参照することができる。
　なお、第２メモリに選択された記号列の長さを記憶する代わりに、0番目の区切りから始まる符号語w0からi番目の区切りから始まる符号語wiまでの符号語に対して選択された記号列の長さの和S(i)を記憶するようにしてもよい。図１３(C)は、この場合における第２メモリの様子を示したものである。第２メモリは、復号対象である符号語を構成する符号語に対応するK個の記号列のうち、選択された記号列の記憶領域の開始位置を示すアドレスと当該選択された記号列までに選択された記号列の長さの和の組を記憶している。このようにすると、出力記号列におけるp番目の記号を容易に参照することが可能となる。具体的には、S(i)≦p<S(i+1)を満たすiを特定することで、p番目の記号を含む記号列を参照することができる。
　以上のように、復号処理の過程で得られる所定の情報を第１メモリ及び第２メモリに記憶することにより、１つの長い記号列である出力記号列の出力処理を省略することができ、復号処理にかかる時間を短縮することが可能となる。特により多くの符号語を並列に復号する場合に有効である。
　なお、上記説明では、第１実施形態や第２実施形態のように複数の符号帳を用いる場合を念頭に説明したが、単一の符号帳を用いる場合でも有効である。この場合、第１メモリは、復号対象である符号語を構成する符号語それぞれに対して単一の符号帳を用いて並列処理により得られる記号列を記憶する（図１４(A)参照）。また、第２メモリは、復号対象である符号語を構成する符号語に対応する記号列の記憶領域の開始位置を示すアドレスと当該記号列の長さの組を記憶する。なお、記号列の記憶領域が第１メモリ上等間隔に配置される場合には、図１４(B)や図１４(C)のように記号列の長さや記号列の長さの和の情報のみを記憶するようにすることができる。
＜第３実施形態＞
　本実施形態では、第１実施形態における復号装置２００に対応する形態について説明する。本実施形態における復号装置２００は、復号対象となる符号語（以下、入力符号語という）を入力とし、当該入力符号語を構成する符号語に対応する記号列を得る。なお、復号装置２００は、得られたすべての記号列を連結することにより得られる記号列を入力符号語に対応する記号列（以下、出力記号列という）として出力するようにしてもよい。
＜＜復号装置２００＞＞
　以下、図１５、図１０を参照して復号装置２００を説明する。図１５は、復号装置２００の構成を示すブロック図である。図１０は、復号装置２００の動作を示すフローチャートである。図１５に示すように復号装置２００は、復号部２１０と、第１メモリ２２０と、第２メモリ２３０と、記録部２９０を含む。記録部２９０は、復号装置２００の処理に必要な情報を適宜記録する構成部である。記録部２９０は、例えば２つの符号帳または解析木T0, T1（ただし、符号帳または解析木T0, T1は入力符号語を得るための符号化処理で用いた符号帳または解析木と同一である）を記録しておく。また、記録部２９０は、例えば開始符号帳または開始解析木に関する情報を記録しておく。第１メモリ２２０は、符号帳または解析木T0, T1を用いて入力符号語を構成する符号語に対応する記号列として得られる記号列を記憶する構成部である。第２メモリ２３０は、入力符号語を構成する符号語に対応する記号列として得られた記号列に関する情報を記憶する構成部である。
　図１０に従い復号装置２００の動作について説明する。ここで、Mを並列処理の単位を表す所定の整数（ただし、Mは2以上の整数）とする。
　Ｓ２１０において、復号部２１０は、２つの符号帳または解析木T0, T1を用いて入力符号語を構成する符号語に対応する記号列を得る。
　復号部２１０は、以下の４つの処理からなる復号処理を実行する。
（１）入力符号語を現在の符号語とし、開始符号帳または開始解析木を現在の符号帳または解析木とする処理
（２）現在の符号語の先頭から２つの符号帳または解析木T0, T1に含まれる符号語の長さと同じ長さの符号語をM個取得し、当該M個の符号語wj(j=0, …, M-1)に対して（２－１）の処理を並列に実行する処理
（２－１）符号帳または解析木Tk(k=0, 1)を用いて、符号語wjと当該符号帳Tkに含まれる符号語を比較し、符号語wjに対応する記号列を候補記号列σ(j, k)として得て、候補記号列σ(j, k)を予め定められたアドレスを開始位置とする第１メモリ２２０の記憶領域に記憶し、候補記号列σ(j, k)を語頭とする記号列（ただし、当該記号列は候補記号列σ(j, k)と異なる）が、符号帳または解析木Tkに含まれる記号列の集合に含まれない場合はT0を次に使用する符号帳または解析木として得て、当該集合に含まれる場合はT1を次に使用する符号帳または解析木として得て、当該次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木Tn(j, k)とする処理
（３）符号語wj(j=0, …, M-1)に対して（３－１）～（３－３）の処理を実行する処理
（３－１）カウンタjを初期化する処理
（３－２）現在の符号帳または解析木が符号帳または解析木Tk(kは0, 1のいずれか)である場合は、候補記号列σ(j, k)を符号語wjに対応する記号列として選択して得て、第１メモリ２２０における当該符号語wjに対応する記号列の記憶領域の開始位置を示すアドレスと当該符号語wjに対応する記号列の長さの組を第２メモリ２３０に記憶し、次に使用する候補符号帳または候補解析木Tn(j, k)を次に使用する符号帳または解析木として選択して得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
（３－３）j<M-1である場合は、カウンタjを1インクリメントし、（３－２）の処理に戻る一方で、それ以外の場合は、現在の符号語から符号語w0 ... wM-1と一致した語頭を除いた符号語を現在の符号語とし、（４）の処理に進む処理
（４）現在の符号語の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は復号処理を終了する処理
　なお、（３－２）の処理において、符号語wjに対応する記号列の長さの代わりに、符号語wjに対応する記号列以前に得られた記号列の長さの合計値を用いるようにしてもよい。
　本発明の実施形態によれば、複数の符号帳または解析木を用いた復号処理にかかる時間を短縮することが可能となる。より詳しくは、複数の符号語に対して当該符号語に対応する記号列の候補と次に使用する符号帳または解析木の候補を取得する処理を並列に実行することにより、符号語に対応する記号列や次に使用する符号帳または解析木を取得するために必要となる処理時間を短縮しながら、複数の符号帳または解析木を用いた復号処理を実行することが可能となる。上記並列処理の効果は、符号帳または解析木のサイズが大きく、記号列の取得に処理時間を要する場合に特に大きいものとなる。また、本発明の実施形態によれば、出力記号列の出力処理を省略することができ、復号処理にかかる時間を短縮することが可能となる。上記出力処理を省略する効果は、より多くの符号語を並列に復号する場合に特に大きいものとなる。
＜第４実施形態＞
　本実施形態では、第２実施形態における復号装置２００に対応する形態について説明する。本実施形態における復号装置２００は、復号対象となる符号語（以下、入力符号語という）を入力とし、当該入力符号語を構成する符号語に対応する記号列を得る。なお、復号装置２００は、得られたすべての記号列を連結することにより得られる記号列を入力符号語に対応する記号列（以下、出力記号列という）として出力するようにしてもよい。
＜＜復号装置２００＞＞
　以下、図１５、図１０を参照して復号装置２００を説明する。図１５は、復号装置２００の構成を示すブロック図である。図１０は、復号装置２００の動作を示すフローチャートである。図１５に示すように復号装置２００は、復号部２１０と、第１メモリ２２０と、第２メモリ２３０と、記録部２９０を含む。記録部２９０は、復号装置２００の処理に必要な情報を適宜記録する構成部である。記録部２９０は、例えば複数の符号帳または解析木{Tk}k=0 K-1（ただし、複数の符号帳または解析木{Tk}k=0 K-1は入力符号語を得るための符号化処理で用いた符号帳または解析木と同一である）を記録しておく。第１メモリ２２０は、複数の符号帳または解析木{Tk}k=0 K-1を用いて入力符号語を構成する符号語に対応する記号列として得られる記号列を記憶する構成部である。第２メモリ２３０は、入力符号語を構成する符号語に対応する記号列として得られた記号列に関する情報を記憶する構成部である。
　図１０に従い復号装置２００の動作について説明する。ここで、Mを並列処理の単位を表す所定の整数（ただし、Mは2以上の整数）とする。
　Ｓ２１０において、復号部２１０は、複数の符号帳または解析木{Tk}k=0 K-1を用いて入力符号語を構成する符号語に対応する記号列を得る。
　復号部２１０は、以下の４つの処理からなる復号処理を実行する。
（１）入力符号語を現在の符号語とし、開始符号帳または開始解析木を現在の符号帳または解析木とする処理
（２）現在の符号語の先頭から複数の符号帳または解析木{Tk}k=0 K-1に含まれる符号語の長さと同じ長さの符号語をM個取得し、当該取得したM個の符号語wj(j=0, …, M-1)に対して（２－１）の処理を並列に実行する処理
（２－１）符号帳または解析木Tk(k=0, ..., K-1)を用いて、符号語wjと当該符号帳Tkに含まれる符号語を比較し、符号語wjに対応する記号列を候補記号列σ(j, k)として得て、候補記号列σ(j, k)を予め定められたアドレスを開始位置とする第１メモリ２２０の記憶領域に記憶し、符号語wjに対応する次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木Tn(j, k)として得る処理
（３）符号語wj(j=0, …, M-1)に対して（３－１）～（３－３）の処理を実行する処理
（３－１）カウンタjを初期化する処理
（３－２）現在の符号帳または解析木が符号帳または解析木Tk(kは0, ..., K-1のいずれか)である場合は、候補記号列σ(j, k)を符号語wjに対応する記号列として選択して得て、第１メモリ２２０における当該符号語wjに対応する記号列の記憶領域の開始位置を示すアドレスと当該符号語wjに対応する記号列の長さの組を第２メモリ２３０に記憶し、次に使用する候補符号帳または候補解析木Tn(j, k)を次に使用する符号帳または解析木として選択して得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
（３－３）j<M-1である場合は、カウンタjを1インクリメントし、（３－２）の処理に戻る一方で、それ以外の場合は、現在の符号語から符号語w0 ... wM-1と一致した語頭を除いた符号語を現在の符号語とし、（４）の処理に進む処理
（４）現在の符号語の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は復号処理を終了する処理
　なお、（３－２）の処理において、符号語wjに対応する記号列の長さの代わりに、符号語wjに対応する記号列以前に得られた記号列の長さの合計値を用いるようにしてもよい。
＜＜変形例＞＞
　第２実施形態の変形例と同様、一部の符号帳または解析木を用いて候補記号列を得るようにしてもよい。この場合、復号部２１０は、Ｓ２１０において以下の４つの処理からなる復号処理を実行することとなる。
（１）入力符号語を現在の符号語とし、開始符号帳または開始解析木を現在の符号帳または解析木とする処理
（２）現在の符号語の先頭から複数の符号帳または解析木{Tk}k=0 K-1に含まれる符号語の長さと同じ長さの符号語をM個取得し、当該取得したM個の符号語wj(j=0, …, M-1)に対して（２－１）の処理を並列に実行する処理
（２－１）符号帳または解析木Tk(k=k(0), ..., k(N-1)、ただし、Nは1以上K-1以下の整数、k(0), ..., k(N-1)は互いに異なる0以上K-1以下の整数)を用いて、符号語wjと当該符号帳または解析木Tkに含まれる符号語を比較し、符号語wjに対応する記号列を候補記号列σ(j, k)として得て、候補記号列σ(j, k)を予め定められたアドレスを開始位置とする第１メモリ２２０の記憶領域に記憶し、符号語wjに対応する次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木Tn(j, k)として得る処理
（３）符号語wj(j=0, …, M-1)に対して（３－１）～（３－３）の処理を実行する処理
（３－１）カウンタjを初期化する処理
（３－２）現在の符号帳または解析木が符号帳または解析木Tk(kはk(0), ..., k(N-1)のいずれか)である場合は、候補記号列σ(j, k)を符号語wjに対応する記号列として選択して得て、第１メモリ２２０における当該符号語wjに対応する記号列の記憶領域の開始位置を示すアドレスと当該符号語wjに対応する記号列の長さの組を第２メモリ２３０に記憶し、次に使用する候補符号帳または候補解析木Tn(j, k)を次に使用する符号帳または解析木として選択して得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とし、それ以外の場合は、符号帳または解析木Tk(kはk(0), ..., k(N-1)のいずれでもない)を用いて、符号語wjと当該符号帳または解析木Tkに含まれる符号語を比較し、符号語wjに対応する記号列を得て、当該符号語wjに対応する記号列を予め定められたアドレスを開始位置とする第１メモリ２２０の記憶領域に記憶し、第１メモリ２２０における当該符号語wjに対応する記号列の記憶領域の開始位置を示すアドレスと当該符号語wjに対応する記号列の長さの組を第２メモリ２３０に記憶し、符号語wjに対応する次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
（３－３）j<M-1である場合は、カウンタjを1インクリメントし、（３－２）の処理に戻る一方で、それ以外の場合は、現在の符号語から符号語w0 ... wM-1と一致した語頭を除いた符号語を現在の符号語とし、（４）の処理に進む処理
（４）現在の符号語の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は復号処理を終了する処理
　なお、（３－２）の処理において、符号語wjに対応する記号列の長さの代わりに、符号語wjに対応する記号列以前に得られた記号列の長さの合計値を用いるようにしてもよい。
　また、第２実施形態の変形例と同様、（２）の処理で対象とする符号帳または解析木は、例えば、記号列の出現に関する確率分布に基づいて、使用される可能性が高いと判断される符号帳または解析木とするとよい。
　また、第３実施形態についても一部の符号帳または解析木を用いて候補記号列を得るようにしてもよい。この場合、（２－１）の処理、（３－２）の処理は以下のようになる。
（２－１）符号帳または解析木Tk(k=k(0)、ただし、k(0)は0以上1以下の整数)を用いて、符号語wjと当該符号帳または解析木Tkに含まれる符号語を比較し、符号語wjに対応する記号列を候補記号列σ(j, k)として得て、候補記号列σ(j, k)を予め定められたアドレスを開始位置とする第１メモリ２２０の記憶領域に記憶し、候補記号列σ(j, k)を語頭とする記号列（ただし、当該記号列は候補記号列σ(j, k)と異なる）が、符号帳または解析木Tkに含まれる記号列の集合に含まれない場合はT0を次に使用する符号帳または解析木として得て、当該集合に含まれる場合はT1を次に使用する符号帳または解析木として得て、当該次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木Tn(j, k)とする処理
（３－２）現在の符号帳または解析木が符号帳または解析木Tk(kはk(0)である)である場合は、候補記号列σ(j, k)を符号語wjに対応する記号列として選択して得て、第１メモリ２２０における当該符号語wjに対応する記号列の記憶領域の開始位置を示すアドレスと当該符号語wjに対応する記号列の長さの組を第２メモリ２３０に記憶し、次に使用する候補符号帳または候補解析木Tn(j, k)を次に使用する符号帳または解析木として選択して得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とし、それ以外の場合は、符号帳Tk(kはk(0)でない)を用いて、符号語wjと当該符号帳または解析木Tkに含まれる符号語を比較し、符号語wjに対応する記号列を得て、当該符号語wjに対応する記号列を予め定められたアドレスを開始位置とする第１メモリ２２０の記憶領域に記憶し、第１メモリ２２０における当該符号語wjに対応する記号列の記憶領域の開始位置を示すアドレスと当該符号語wjに対応する記号列の長さの組を第２メモリ２３０に記憶し、符号語wjに対応する記号列を語頭とする記号列（ただし、当該記号列は符号語wjに対応する記号列と異なる）が、符号帳または解析木Tkに含まれる記号列の集合に含まれない場合はT0を次に使用する符号帳または解析木として得て、当該集合に含まれる場合はT1を次に使用する符号帳または解析木として得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
　なお、（３－２）の処理において、符号語wjに対応する記号列の長さの代わりに、符号語wjに対応する記号列以前に得られた記号列の長さの合計値を用いるようにしてもよい。
　本発明の実施形態によれば、複数の符号帳または解析木を用いた復号処理にかかる時間を短縮することが可能となる。より詳しくは、複数の符号語に対して当該符号語に対応する記号列の候補と次に使用する符号帳または解析木の候補を取得する処理を並列に実行することにより、符号語に対応する記号列や次に使用する符号帳または解析木を取得するために必要となる処理時間を短縮しながら、複数の符号帳または解析木を用いた復号処理を実行することが可能となる。上記並列処理の効果は、符号帳または解析木のサイズが大きく、記号列の取得に処理時間を要する場合に特に大きいものとなる。また、本発明の実施形態によれば、出力記号列の出力処理を省略することができ、復号処理にかかる時間を短縮することが可能となる。上記出力処理を省略する効果は、より多くの符号語を並列に復号する場合に特に大きいものとなる。
＜第３実施形態や第４実施形態における復号部２１０＞
　第３実施形態や第４実施形態における復号部２１０は、所定の符号帳または解析木の切り替え規則に基づいて複数の符号帳または解析木を用いて復号処理を実行している。詳しくは、復号部２１０は、以下の２つの処理から構成される処理を繰り返し実行するものであるといえる。
（１）入力符号語を構成する複数の符号語に対して、
　複数の符号帳または解析木に含まれる１以上の所定の符号帳または解析木を用いて符号語に対応する記号列を候補記号列として得て、当該候補記号列を予め定められたアドレスを開始位置とする第１メモリ２２０の記憶領域に記憶し、符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木として得る処理
　を並列に実行する処理
（２）入力符号語を構成する複数の符号語に対して、
　符号語に対して得られた候補記号列と次に使用する候補符号帳または候補解析木の組と、現在の符号帳または解析木と、符号帳または解析木の切り替え規則とに基づいて、当該符号語に対応する記号列と次に使用する符号帳または解析木の組を得て、第１メモリ２２０における当該符号語に対応する記号列の記憶領域の開始位置を示すアドレスと当該符号語に対応する記号列の長さまたは当該符号語に対応する記号列以前に得られた記号列の長さの合計値の組を第２メモリ２３０に記憶し、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
　を逐次実行する処理
　なお、＜技術的背景＞で説明したように、得られた記号列や当該記号列に関する情報を記憶する第１メモリ２２０や第２メモリ２３０を用いることにより出力記号列の出力処理を省略する方法は、単一の符号帳を用いる場合にも適用することができる。この場合、復号部２１０は、１以上の符号帳または解析木を用いて復号処理を実行する。詳しくは、復号部２１０は、以下の２つの処理から構成される処理を繰り返し実行するものであるといえる。
（１）入力符号語を構成する複数の符号語に対して、
　１以上の符号帳または解析木に含まれる１以上の所定の符号帳または解析木を用いて符号語に対応する記号列を得て、当該符号語に対応する記号列を予め定められたアドレスを開始位置とする第１メモリ２２０の記憶領域に記憶する処理
　を並列に実行する処理
（２）入力符号語を構成する複数の符号語に対して、
　第１メモリ２２０における当該符号語に対応する記号列の記憶領域を特定するための情報を第２メモリ２３０に記憶する処理
　を実行する処理
　したがって、第３実施形態、第４実施形態における復号処理についてまとめると、以下のようになる。
［１］　復号対象となる符号語（以下、入力符号語という）を入力とし、
　１以上の符号帳または解析木（ただし、当該１以上の符号帳または解析木は前記入力符号語を得るための符号化処理で用いた１以上の符号帳または解析木と同一である）を用いて前記入力符号語を構成する符号語に対応する記号列を得る復号部と、
　前記１以上の符号帳または解析木を用いて前記入力符号語を構成する符号語に対応する記号列として得られる記号列を記憶する第１メモリと、
　前記入力符号語を構成する符号語に対応する記号列として得られた記号列に関する情報を記憶する第２メモリと、
　を含む復号装置であって、
　前記１以上の符号帳または解析木は、少なくとも記号列と符号語とを含む組から構成され、
　前記１以上の符号帳または解析木に含まれる符号語はすべて長さが同じであり、
　前記復号部は、
　前記入力符号語を構成する複数の符号語に対して、
　前記１以上の符号帳または解析木に含まれる１以上の所定の符号帳または解析木を用いて符号語に対応する記号列を得て、当該符号語に対応する記号列を予め定められたアドレスを開始位置とする前記第１メモリの記憶領域に記憶する処理
　を並列に実行する処理と、
　前記入力符号語を構成する複数の符号語に対して、
　前記第１メモリにおける当該符号語に対応する記号列の記憶領域を特定するための情報を前記第２メモリに記憶する処理
　を実行する処理と、
　から構成される処理を繰り返し実行する
　復号装置。
［２］　［１］に記載の復号装置であって、
　{Tk}k=0 K-1（ただし、Kは2以上の整数）を前記１以上の符号帳または解析木、Mを並列処理の単位を表す所定の整数（ただし、Mは2以上の整数）とし、
　前記復号部は、
　前記入力符号語を構成する複数の符号語に対して、
　前記１以上の符号帳または解析木に含まれる１以上の所定の符号帳または解析木を用いて符号語に対応する記号列を候補記号列として得て、当該候補記号列を予め定められたアドレスを開始位置とする前記第１メモリの記憶領域に記憶し、符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木として得る処理
　を並列に実行する処理と、
　前記入力符号語を構成する複数の符号語に対して、
　符号語に対して前記得られた候補記号列と次に使用する候補符号帳または候補解析木の組と、現在の符号帳または解析木と、前記符号帳または解析木の切り替え規則とに基づいて、当該符号語に対応する記号列と次に使用する符号帳または解析木の組を得て、前記第１メモリにおける当該符号語に対応する記号列の記憶領域の開始位置を示すアドレスと当該符号語に対応する記号列の長さまたは当該符号語に対応する記号列以前に得られた記号列の長さの合計値の組を前記第２メモリに記憶し、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
　を逐次実行する処理と、
　から構成される処理を繰り返し実行する
　復号装置。
［３］　［２］に記載の復号装置であって、
　前記復号部は、
（１）前記入力符号語を現在の符号語とし、開始符号帳または開始解析木（ただし、当該開始符号帳または開始解析木は１以上の符号帳または解析木{Tk}k=0 K-1のいずれかである）を現在の符号帳または解析木とする処理と、
（２）現在の符号語の先頭から１以上の符号帳または解析木{Tk}k=0 K-1に含まれる符号語の長さと同じ長さの符号語をM個取得し、当該取得したM個の符号語wj(j=0, …, M-1)に対して（２－１）の処理を並列に実行する処理と、
（２－１）符号帳または解析木Tk(k=0, ..., K-1)を用いて、符号語wjと当該符号帳または解析木Tkに含まれる符号語を比較し、符号語wjに対応する記号列を候補記号列σ(j, k)として得て、候補記号列σ(j, k)を予め定められたアドレスを開始位置とする前記第１メモリの記憶領域に記憶し、前記符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木Tn(j, k)として得る処理
（３）符号語wj(j=0, …, M-1)に対して（３－１）～（３－３）の処理を実行する処理と、
（３－１）カウンタjを初期化する処理
（３－２）現在の符号帳または解析木が符号帳または解析木Tk(kは0, ..., K-1のいずれか)である場合は、候補記号列σ(j, k)を符号語wjに対応する記号列として選択して得て、前記第１メモリにおける当該符号語wjに対応する記号列の記憶領域の開始位置を示すアドレスと当該符号語wjに対応する記号列の長さまたは当該符号語wjに対応する記号列以前に得られた記号列の長さの合計値の組を前記第２メモリに記憶し、次に使用する候補符号帳または候補解析木Tn(j, k)を次に使用する符号帳または解析木として選択して得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
（３－３）j<M-1である場合は、カウンタjを1インクリメントし、（３－２）の処理に戻る一方で、それ以外の場合は、現在の符号語から符号語w0 ... wM-1と一致した語頭を除いた符号語を現在の符号語とし、（４）の処理に進む処理
（４）現在の符号語の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は復号処理を終了する処理と
　を実行する
　ことを特徴とする復号装置。
［４］　［３］に記載の復号装置であって、
　符号帳または解析木Tk(k=0, 1 ,…, K-1)は、
　記号列と符号語と次に使用する符号帳または解析木の３つ組から構成され、記号列の集合である記号列モードが割り当てられたものであり、
　当該符号帳または解析木Tkの展開記号列は当該符号帳または解析木Tkに割り当てられた記号列モードに含まれるいずれかの記号列を語頭とするという条件を満たすものであり、
　前記符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を得る処理は、符号帳または解析木Tkを用いて、符号語wjに対応する次に使用する符号帳または解析木を得る処理である
　ことを特徴とする復号装置。
［５］　［２］に記載の復号装置であって、
　前記復号部は、
（１）前記入力符号語を現在の符号語とし、開始符号帳または開始解析木（ただし、当該開始符号帳または開始解析木は１以上の符号帳または解析木{Tk}k=0 K-1のいずれかである）を現在の符号帳または解析木とする処理と、
（２）現在の符号語の先頭から１以上の符号帳または解析木{Tk}k=0 K-1に含まれる符号語の長さと同じ長さの符号語をM個取得し、当該取得したM個の符号語wj(j=0, …, M-1)に対して（２－１）の処理を並列に実行する処理と、
（２－１）符号帳または解析木Tk(k=k(0), ..., k(N-1)、ただし、Nは1以上K-1以下の整数、k(0), ..., k(N-1)は互いに異なる0以上K-1以下の整数)を用いて、符号語wjと当該符号帳または解析木Tkに含まれる符号語を比較し、符号語wjに対応する記号列を候補記号列σ(j, k)として得て、候補記号列σ(j, k)を予め定められたアドレスを開始位置とする前記第１メモリの記憶領域に記憶し、前記符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木Tn(j, k)として得る処理
（３）符号語wj(j=0, …, M-1)に対して（３－１）～（３－３）の処理を実行する処理と、
（３－１）カウンタjを初期化する処理
（３－２）現在の符号帳または解析木が符号帳または解析木Tk(kはk(0), ..., k(N-1)のいずれか)である場合は、候補記号列σ(j, k)を符号語wjに対応する記号列として選択して得て、前記第１メモリにおける当該符号語wjに対応する記号列の記憶領域の開始位置を示すアドレスと当該符号語wjに対応する記号列の長さまたは当該符号語wjに対応する記号列以前に得られた記号列の長さの合計値の組を前記第２メモリに記憶し、次に使用する候補符号帳または候補解析木Tn(j, k)を次に使用する符号帳または解析木として選択して得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とし、それ以外の場合は、符号帳または解析木Tk(kはk(0), ..., k(N-1)のいずれでもない)を用いて、符号語wjと当該符号帳または解析木Tkに含まれる符号語を比較し、符号語wjに対応する記号列を得て、当該符号語wjに対応する記号列を予め定められたアドレスを開始位置とする前記第１メモリの記憶領域に記憶し、前記第１メモリにおける当該符号語wjに対応する記号列の記憶領域の開始位置を示すアドレスと当該符号語wjに対応する記号列の長さまたは当該符号語wjに対応する記号列以前に得られた記号列の長さの合計値の組を前記第２メモリに記憶し、前記符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
（３－３）j<M-1である場合は、カウンタjを1インクリメントし、（３－２）の処理に戻る一方で、それ以外の場合は、現在の符号語から符号語w0 ... wM-1と一致した語頭を除いた符号語を現在の符号語とし、（４）の処理に進む処理
（４）現在の符号語の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は復号処理を終了する処理と
　を実行する
　ことを特徴とする復号装置。
［６］　［５］に記載の復号装置であって、
　符号帳または解析木Tk(k=0, 1 ,…, K-1)は、
　記号列と符号語と次に使用する符号帳または解析木の３つ組から構成され、記号列の集合である記号列モードが割り当てられたものであり、
　当該符号帳または解析木Tkの展開記号列は当該符号帳または解析木Tkに割り当てられた記号列モードに含まれるいずれかの記号列を語頭とするという条件を満たすものであり、
　前記符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を得る処理は、符号帳または解析木Tkを用いて、符号語wjに対応する次に使用する符号帳または解析木を得る処理である
　ことを特徴とする復号装置。
［７］　復号装置が、復号対象となる符号語（以下、入力符号語という）を入力とし、
　１以上の符号帳または解析木（ただし、当該１以上の符号帳または解析木は前記入力符号語を得るための符号化処理で用いた１以上の符号帳または解析木と同一である）を用いて前記入力符号語を構成する符号語に対応する記号列を得る復号ステップと、
　を含む復号方法であって、
　前記復号装置は、前記１以上の符号帳または解析木を用いて前記入力符号語を構成する符号語に対応する記号列として得られる記号列を記憶する第１メモリと、
　前記入力符号語を構成する符号語に対応する記号列として得られた記号列に関する情報を記憶する第２メモリと、
　を含むものであり
　前記１以上の符号帳または解析木は、少なくとも記号列と符号語とを含む組から構成され、
　前記１以上の符号帳または解析木に含まれる符号語はすべて長さが同じであり、
　前記復号ステップは、
　前記入力符号語を構成する複数の符号語に対して、
　前記１以上の符号帳または解析木に含まれる１以上の所定の符号帳または解析木を用いて符号語に対応する記号列を得て、当該符号語に対応する記号列を予め定められたアドレスを開始位置とする前記第１メモリの記憶領域に記憶する処理
　を並列に実行する処理と、
　前記入力符号語を構成する複数の符号語に対して、
　前記第１メモリにおける当該符号語に対応する記号列の記憶領域を特定するための情報を前記第２メモリに記憶する処理
　を実行する処理と、
　から構成される処理を繰り返し実行する
　復号方法。
［８］　［１］ないし［６］のいずれか１つに記載の復号装置のいずれかとしてコンピュータを機能させるためのプログラム。
＜補記＞
　本明細書中に記載されている構成要素により実現される機能は、当該記載された機能を実現するようにプログラムされた、汎用プロセッサ、特定用途プロセッサ、集積回路、ＡＳＩＣｓ(Application Specific Integrated Circuits)、ＣＰＵ(Central Processing Unit)、従来型の回路、および／又はそれらの組合せを含む、circuitry又はprocessing circuitryにおいて実装されてもよい。プロセッサは、トランジスタやその他の回路を含み、circuitry又はprocessing circuitryとみなされる。プロセッサは、メモリに格納されたプログラムを実行する、programmed processorであってもよい。
　本明細書において、circuitry、ユニット、手段は、記載された機能を実現するようにプログラムされたハードウェア、又は実行するハードウェアである。当該ハードウェアは、本明細書に開示されているあらゆるハードウェア、又は、当該記載された機能を実現するようにプログラムされた、又は、実行するものとして知られているあらゆるハードウェアであってもよい。
　当該ハードウェアがcircuitryのタイプであるとみなされるプロセッサである場合、当該circuitry、手段、又はユニットは、ハードウェアと、当該ハードウェア及び又はプロセッサを構成する為に用いられるソフトウェアの組合せである。
　上述の各種の処理は、図１６に示すコンピュータ２０００の記録部２０２０に、上記方法の各ステップを実行させるプログラムを読み込ませ、制御部２０１０、入力部２０３０、出力部２０４０、表示部２０５０などに動作させることで実施できる。
　この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
　また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ－ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
　このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって処理を実行する構成としてもよい。さらには、サーバコンピュータの一部をプログラムと共にユーザに使用させる、いわゆるＳａａＳ（Software as a Service）型のサービスを利用して、端末の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
　また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
　本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。

Claims (8)

  1. 　復号対象となる符号語（以下、入力符号語という）を入力とし、当該入力符号語に対応する記号列（以下、出力記号列という）を出力する復号装置であって、
    　複数の符号帳または解析木（ただし、当該複数の符号帳または解析木は前記入力符号語を得るための符号化処理で用いた複数の符号帳または解析木と同一である）を用いて前記入力符号語を構成する符号語に対応する記号列を得て、得られた記号列を連結して得られる記号列を前記出力記号列として出力する復号部を含み、
    　前記複数の符号帳または解析木は、少なくとも記号列と符号語とを含む組から構成され、
    　前記複数の符号帳または解析木に含まれる符号語はすべて長さが同じであり、
    　前記復号部は、
    　前記入力符号語を構成する複数の符号語に対して、
    　前記複数の符号帳または解析木に含まれる１以上の所定の符号帳または解析木を用いて符号語に対応する記号列を候補記号列として得て、符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木として得る処理
    　を並列に実行する処理と、
    　前記入力符号語を構成する複数の符号語に対して、
    　符号語に対して前記得られた候補記号列と次に使用する候補符号帳または候補解析木の組と、現在の符号帳または解析木と、前記符号帳または解析木の切り替え規則とに基づいて、当該符号語に対応する記号列と次に使用する符号帳または解析木の組を得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
    　を逐次実行する処理と、
    　から構成される処理を繰り返し実行することにより、前記出力記号列を得る
    　復号装置。
  2. 　請求項１に記載の復号装置であって、
    　{Tk}k=0 K-1（ただし、Kは2以上の整数）を前記複数の符号帳または解析木、Mを並列処理の単位を表す所定の整数（ただし、Mは2以上の整数）とし、
    　前記復号部は、
    （１）前記入力符号語を現在の符号語とし、開始符号帳または開始解析木（ただし、当該開始符号帳または開始解析木は複数の符号帳または解析木{Tk}k=0 K-1のいずれかである）を現在の符号帳または解析木とする処理と、
    （２）現在の符号語の先頭から複数の符号帳または解析木{Tk}k=0 K-1に含まれる符号語の長さと同じ長さの符号語をM個取得し、当該取得したM個の符号語wj(j=0, …, M-1)に対して（２－１）の処理を並列に実行する処理と、
    （２－１）符号帳または解析木Tk(k=0, ..., K-1)を用いて、符号語wjと当該符号帳または解析木Tkに含まれる符号語を比較し、符号語wjに対応する記号列を候補記号列σ(j, k)として得て、前記符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木Tn(j, k)として得る処理
    （３）符号語wj(j=0, …, M-1)に対して（３－１）～（３－３）の処理を実行する処理と、
    （３－１）カウンタjを初期化する処理
    （３－２）現在の符号帳または解析木が符号帳または解析木Tk(kは0, ..., K-1のいずれか)である場合は、候補記号列σ(j, k)を符号語wjに対応する記号列として選択して得て、次に使用する候補符号帳または候補解析木Tn(j, k)を次に使用する符号帳または解析木として選択して得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
    （３－３）j<M-1である場合は、カウンタjを1インクリメントし、（３－２）の処理に戻る一方で、それ以外の場合は、現在の符号語から符号語w0 ... wM-1と一致した語頭を除いた符号語を現在の符号語とし、（４）の処理に進む処理
    （４）現在の符号語の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は（３－２）の処理により得られたすべての記号列を連結して得られる記号列を前記出力記号列として出力し復号処理を終了する処理と
    　を実行する
    　ことを特徴とする復号装置。
  3. 　請求項２に記載の復号装置であって、
    　符号帳または解析木Tk(k=0, 1 ,…, K-1)は、
    　記号列と符号語と次に使用する符号帳または解析木の３つ組から構成され、記号列の集合である記号列モードが割り当てられたものであり、
    　当該符号帳または解析木Tkの展開記号列は当該符号帳または解析木Tkに割り当てられた記号列モードに含まれるいずれかの記号列を語頭とするという条件を満たすものであり、
    　前記符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を得る処理は、符号帳または解析木Tkを用いて、符号語wjに対応する次に使用する符号帳または解析木を得る処理である
    　ことを特徴とする復号装置。
  4. 　請求項１に記載の復号装置であって、
    　{Tk}k=0 K-1（ただし、Kは2以上の整数）を前記複数の符号帳または解析木、Mを並列処理の単位を表す所定の整数（ただし、Mは2以上の整数）とし、
    　前記復号部は、
    （１）前記入力符号語を現在の符号語とし、開始符号帳または開始解析木（ただし、当該開始符号帳または開始解析木は複数の符号帳または解析木{Tk}k=0 K-1のいずれかである）を現在の符号帳または解析木とする処理と、
    （２）現在の符号語の先頭から複数の符号帳または解析木{Tk}k=0 K-1に含まれる符号語の長さと同じ長さの符号語をM個取得し、当該取得したM個の符号語wj(j=0, …, M-1)に対して（２－１）の処理を並列に実行する処理と、
    （２－１）符号帳または解析木Tk(k=k(0), ..., k(N-1)、ただし、Nは1以上K-1以下の整数、k(0), ..., k(N-1)は互いに異なる0以上K-1以下の整数)を用いて、符号語wjと当該符号帳または解析木Tkに含まれる符号語を比較し、符号語wjに対応する記号列を候補記号列σ(j, k)として得て、前記符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木Tn(j, k)として得る処理
    （３）符号語wj(j=0, …, M-1)に対して（３－１）～（３－３）の処理を実行する処理と、
    （３－１）カウンタjを初期化する処理
    （３－２）現在の符号帳または解析木が符号帳または解析木Tk(kはk(0), ..., k(N-1)のいずれか)である場合は、候補記号列σ(j, k)を符号語wjに対応する記号列として選択して得て、次に使用する候補符号帳または候補解析木Tn(j, k)を次に使用する符号帳または解析木として選択して得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とし、それ以外の場合は、符号帳または解析木Tk(kはk(0), ..., k(N-1)のいずれでもない)を用いて、符号語wjと当該符号帳または解析木Tkに含まれる符号語を比較し、符号語wjに対応する記号列を得て、前記符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
    （３－３）j<M-1である場合は、カウンタjを1インクリメントし、（３－２）の処理に戻る一方で、それ以外の場合は、現在の符号語から符号語w0 ... wM-1と一致した語頭を除いた符号語を現在の符号語とし、（４）の処理に進む処理
    （４）現在の符号語の長さが0でない場合は（２）の処理に戻る一方で、それ以外の場合は（３－２）の処理により得られたすべての記号列を連結して得られる記号列を前記出力記号列として出力し復号処理を終了する処理と
    　を実行する
    　ことを特徴とする復号装置。
  5. 　請求項４に記載の復号装置であって、
    　符号帳または解析木Tk(k=0, 1 ,…, K-1)は、
    　記号列と符号語と次に使用する符号帳または解析木の３つ組から構成され、記号列の集合である記号列モードが割り当てられたものであり、
    　当該符号帳または解析木Tkの展開記号列は当該符号帳または解析木Tkに割り当てられた記号列モードに含まれるいずれかの記号列を語頭とするという条件を満たすものであり、
    　前記符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を得る処理は、符号帳または解析木Tkを用いて、符号語wjに対応する次に使用する符号帳または解析木を得る処理である
    　ことを特徴とする復号装置。
  6. 　請求項４に記載の復号装置であって、
    　符号帳または解析木Tk(k=k(0), ..., k(N-1))は、記号列の出現に関する確率分布に基づいて、使用される可能性が高いと判断される符号帳または解析木である
    　ことを特徴とする復号装置。
  7. 　復号装置が、復号対象となる符号語（以下、入力符号語という）を入力とし、当該入力符号語に対応する記号列（以下、出力記号列という）を出力する復号方法であって、
    　前記復号装置が、複数の符号帳または解析木（ただし、当該複数の符号帳または解析木は前記入力符号語を得るための符号化処理で用いた複数の符号帳または解析木と同一である）を用いて前記入力符号語を構成する符号語に対応する記号列を得て、得られた記号列を連結して得られる記号列を前記出力記号列として出力する復号ステップを含み、
    　前記複数の符号帳または解析木は、少なくとも記号列と符号語とを含む組から構成され、
    　前記複数の符号帳または解析木に含まれる符号語はすべて長さが同じであり、
    　前記復号ステップは、
    　前記入力符号語を構成する複数の符号語に対して、
    　前記複数の符号帳または解析木に含まれる１以上の所定の符号帳または解析木を用いて符号語に対応する記号列を候補記号列として得て、符号帳または解析木の切り替え規則に基づいて次に使用する符号帳または解析木を次に使用する候補符号帳または候補解析木として得る処理
    　を並列に実行する処理と、
    　前記入力符号語を構成する複数の符号語に対して、
    　符号語に対して前記得られた候補記号列と次に使用する候補符号帳または候補解析木の組と、現在の符号帳または解析木と、前記符号帳または解析木の切り替え規則とに基づいて、当該符号語に対応する記号列と次に使用する符号帳または解析木の組を得て、当該次に使用する符号帳または解析木を現在の符号帳または解析木とする処理
    　を逐次実行する処理と、
    　から構成される処理を繰り返し実行することにより、前記出力記号列を得る
    　復号方法。
  8. 　請求項１ないし６のいずれか１項に記載の復号装置のいずれかとしてコンピュータを機能させるためのプログラム。
PCT/JP2024/006542 2024-02-22 2024-02-22 復号装置、復号方法、プログラム Pending WO2025177531A1 (ja)

Priority Applications (1)

Application Number Priority Date Filing Date Title
PCT/JP2024/006542 WO2025177531A1 (ja) 2024-02-22 2024-02-22 復号装置、復号方法、プログラム

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/JP2024/006542 WO2025177531A1 (ja) 2024-02-22 2024-02-22 復号装置、復号方法、プログラム

Publications (1)

Publication Number Publication Date
WO2025177531A1 true WO2025177531A1 (ja) 2025-08-28

Family

ID=96846650

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2024/006542 Pending WO2025177531A1 (ja) 2024-02-22 2024-02-22 復号装置、復号方法、プログラム

Country Status (1)

Country Link
WO (1) WO2025177531A1 (ja)

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2001086513A (ja) * 1999-07-09 2001-03-30 Fuji Xerox Co Ltd 符号化装置、復号装置、符号変換テーブル生成方法、および符号化方法ならびに復号方法
JP2017118547A (ja) * 2011-01-14 2017-06-29 ジーイー ビデオ コンプレッション エルエルシー エントロピー符号化および復号化スキーム

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2001086513A (ja) * 1999-07-09 2001-03-30 Fuji Xerox Co Ltd 符号化装置、復号装置、符号変換テーブル生成方法、および符号化方法ならびに復号方法
JP2017118547A (ja) * 2011-01-14 2017-06-29 ジーイー ビデオ コンプレッション エルエルシー エントロピー符号化および復号化スキーム

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
DUBE, DANNY ET AL.: "Individually Optimal Single- and Multiple-Tree Almost Instantaneous Variable-to-Fixed Codes, 2018", IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT, 17 June 2018 (2018-06-17), pages 2192 - 2196, XP033385625, Retrieved from the Internet <URL:https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8437665> [retrieved on 20240404], DOI: 10.1109/ISIT.2018.8437665 *

Similar Documents

Publication Publication Date Title
JP3974036B2 (ja) ハフマン・デコーディングを実施する方法
US5150430A (en) Lossless data compression circuit and method
US6385617B1 (en) Method and apparatus for creating and manipulating a compressed binary decision diagram in a data processing system
JP3778087B2 (ja) データ符号化装置及びデータ復号装置
JPH07283739A (ja) 短ブロックのデータを圧縮、伸長するための方法、及び装置
US11677416B2 (en) Hardware implementable data compression/decompression algorithm
JP3714935B2 (ja) 改善されたハフマンデコーディング方法及び装置
JP2004525537A (ja) ハフマン・コード長情報を生成する方法
JP5413153B2 (ja) データ圧縮装置、データ伸長装置、データ圧縮プログラム、及びデータ伸長プログラム
US9673836B1 (en) System level testing of entropy encoding
WO2025177531A1 (ja) 復号装置、復号方法、プログラム
WO2025163695A1 (ja) 符号化装置、復号装置、符号化方法、復号方法、データ構造、プログラム
WO2025169470A1 (ja) 復号装置、復号方法、およびプログラム
WO2025169479A1 (ja) 符号化装置、復号装置、符号化方法、復号方法、プログラム
WO2025158631A1 (ja) 符号化装置、復号装置、符号化方法、復号方法、データ構造、プログラム
WO2025173103A1 (ja) 符号化装置、符号化方法、符号化プログラム
WO2024185041A1 (ja) 符号化装置、復号装置、符号化方法、復号方法、データ構造、プログラム
JP7584579B2 (ja) 受信したデータを処理する装置
JP6276386B2 (ja) データ構造、情報処理装置、情報処理方法、及びプログラム記録媒体
JP3565147B2 (ja) 復号装置
JP2025024868A (ja) デコーダ、エンコーダ、デコード方法、及びエンコード方法
JP2002076907A (ja) 可変長符号化データの復号化方法及び可変長符号化データの復号化装置並びに可変長符号化データの復号化処理プログラムを記録した記録媒体
KR101270633B1 (ko) 복수 호프만 테이블을 적용하여 고속 처리가 가능한 멀티미디어용 호프만 디코딩 방법 및 장치
Gueniche et al. WBPL: An Open-Source Library for Predicting Web Surfing Behaviors
JPH11177438A (ja) 情報変換装置

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 24925863

Country of ref document: EP

Kind code of ref document: A1