Paper Abstract and Keywords |
Presentation |
2010-03-05 14:15
Antidictionary Coding Scheme Based on Array Structures Keita Suzuki, Hirotada Fukae (Univ. of Electro-Comm.), Takahiro Ota (Nagano Prefectural Inst. of Tech.), Hiroyoshi Morita (Univ. of Electro-Comm.) IT2009-124 ISEC2009-132 WBS2009-103 |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
Given a string over a finite alphabet, a set of minimal forbidden words (MFW) that do not appear in the
string is called an antidictionary. A coding scheme used an antidictionary automaton was proposed by Crochemore
in 2000. The antidictionary automaton represents the string symbol by symbol by using the antidictionary. In this
article, we present an algorithm to build the antidictionary automaton for a given string. The proposed algorithm
is fully based on array data structure. Computer simulation results show that the proposed algorithm has a linear
time and memory complexities proportional to the length of the string and these complexities are significantly less
than those of the conventional algorithm based on tree data structure. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
antidictionary / data compression / coding / array / / / / |
Reference Info. |
IEICE Tech. Rep., vol. 109, no. 444, IT2009-124, pp. 343-348, March 2010. |
Paper # |
IT2009-124 |
Date of Issue |
2010-02-25 (IT, ISEC, WBS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
Download PDF |
IT2009-124 ISEC2009-132 WBS2009-103 |
Conference Information |
Committee |
IT ISEC WBS |
Conference Date |
2010-03-04 - 2010-03-05 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Nagano-Engineering Campus, Shinshu University |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
|
Paper Information |
Registration To |
IT |
Conference Code |
2010-03-IT-ISEC-WBS |
Language |
Japanese |
Title (in Japanese) |
(See Japanese page) |
Sub Title (in Japanese) |
(See Japanese page) |
Title (in English) |
Antidictionary Coding Scheme Based on Array Structures |
Sub Title (in English) |
|
Keyword(1) |
antidictionary |
Keyword(2) |
data compression |
Keyword(3) |
coding |
Keyword(4) |
array |
Keyword(5) |
|
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Keita Suzuki |
1st Author's Affiliation |
University. of Electro-Communication. (Univ. of Electro-Comm.) |
2nd Author's Name |
Hirotada Fukae |
2nd Author's Affiliation |
University. of Electro-Communication. (Univ. of Electro-Comm.) |
3rd Author's Name |
Takahiro Ota |
3rd Author's Affiliation |
Nagano Prefectural Institute of Technology (Nagano Prefectural Inst. of Tech.) |
4th Author's Name |
Hiroyoshi Morita |
4th Author's Affiliation |
University. of Electro-Communication. (Univ. of Electro-Comm.) |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-1 |
Date Time |
2010-03-05 14:15:00 |
Presentation Time |
25 minutes |
Registration for |
IT |
Paper # |
IT2009-124, ISEC2009-132, WBS2009-103 |
Volume (vol) |
vol.109 |
Number (no) |
no.444(IT), no.445(ISEC), no.446(WBS) |
Page |
pp.343-348 |
#Pages |
6 |
Date of Issue |
2010-02-25 (IT, ISEC, WBS) |
|