http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
- 中文 을 입력하시려면 zhongwen을 입력하시고 space를누르시면됩니다.
- 北京 을 입력하시려면 beijing을 입력하시고 space를 누르시면 됩니다.
RISS 인기검색어
- 검색키워드
- 주제어 : Compressed suffix arrays (검색결과 5 건)
- 무료
- 기관 내 무료
- 유료
-
Comparisons of Practical Performance for Constructing Compressed Suffix Arrays
박치성(Chi Seong Park),김민환(Min Hwan Kim),이석환(Suk Hwan Lee),권기룡(Ki Ryong Kwon),김동규(Dong Kyue Kim) 한국정보과학회 2007 정보과학회논문지 : 시스템 및 이론 Vol.34 No.5·6
써픽스 배열은 기본적인 전체 텍스트 인덱스 자료구조로서, 반복되는 패턴 질의 수행 시 효율적으로 사용될 수 있다. 유용한 전체 텍스트 인덱스 자료구조들이 많이 제안되어왔음에도 불구하고, O(nlogn)-비트 공간을 필요로 하는 공통적인 문제점으로 인하여 보다 효율적으로 공간을 사용할 수 있는 방법에 대한 필요성이 요구되었다. 하지만 기 개발된 압축된 써픽스 배열이나 FM-인덱스와 같은 것들 또한 이미 존재하는 써픽스 배열에서부터 구축되어야 하기 때문에 실제적인 사용 공간을 줄일 수는 없었다. 최근, 써픽스 배열을 구축할 필요 없이 텍스트로부터 직접 압축된 써픽스 배열을 구축할 수 있는 두 가지 알고리즘들이 제안되었다. 본 논문에서는 실험을 통해 자료구조 구축 시간과 구축 시 필요로 하는 최대사용 공간, 구축이 끝난 후 최종 자료구조의 크기 등을 측정함으로써 이 두 가지 압축된 써픽스 배열 구축 알고리즘과 기존의 써픽스 배열들과의 실제적인 성능을 비교한다. Suffix arrays, fundamental full-text index data structures, can be efficiently used where patterns are queried many times. Although many useful full-text index data structures have been proposed, their O(nlogn)-bit space consumption motivates researchers to develop more space-efficient ones. However, their space efficient versions such as the compressed suffix array and the FM-index have been developed; those can not reduce the practical working space because their constructions are based on the existing suffix array. Recently, two direct construction algorithms of compressed suffix arrays from the text without constructing the suffix array have been proposed. In this paper, we compare practical performance of these algorithms of compressed suffix arrays with that of various algorithms of suffix arrays by measuring the construction times, the peak memory usages during construction and the sizes of their final outputs.
-
Na, Joong Chae,Park, Kunsoo Elsevier 2007 Theoretical computer science Vol.385 No.1-3
<P><B>Abstract</B></P><P>The <I>suffix array</I> is a fundamental index data structure in string algorithms and bioinformatics, and the <I>compressed suffix array (CSA)</I> and the <I>FM-index</I> are its compressed versions. Many algorithms for constructing these index data structures have been developed. Recently, Hon et al. [W.K. Hon, K. Sadakane, W.K. Sung, Breaking a time-and-space barrier in constructing full-text indices, in: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 251–260] proposed a construction algorithm using O(nloglog|Σ|) time and O(nlog|Σ|)-bit working space, which is the fastest algorithm using O(nlog|Σ|)-bit working space.</P><P>In this paper we give an efficient algorithm to construct the index data structures. Our algorithm constructs the suffix array, the CSA, the FM-index, and Burrows–Wheeler transform using alphabet-independent O(n) time and O(nlog|Σ|log|Σ|αn)-bit working space, where α=<SUB>log3</SUB>2. Our algorithm takes less time and more space than Hon et al.’s algorithm. Our algorithm uses least working space among alphabet-independent linear-time algorithms.</P>
-
Improving Lookup Time Complexity of Compressed Suffix Arrays using Multi-ary Wavelet Tree
Zheng Wu,Joong Chae Na,Minhwan Kim,Dong Kyue Kim 한국정보과학회 2009 Journal of Computing Science and Engineering Vol.3 No.1
In a given text T of size n, we need to search for the information that we are interested. In order to support fast searching, an index must be constructed by preprocessing the text. Suffix array is a kind of index data structure. The compressed suffix array (CSA) is one of the compressed indices based on the regularity of the suffix array, and can be compressed to the k<SUP>th</SUP> order empirical entropy. In this paper we improve the lookup time complexity of the compressed suffix array by using the multi-ary wavelet tree at the cost of more space. In our implementation, the lookup time complexity of the compressed suffix array is O(log<SUP>ε/(1-ε)</SUP>σn logr σ), and the space of the compressed suffix array is ε?¹ nHk(T) + O(n log log n/log<SUP>ε</SUP>σ n) bits, where σ is the size of alphabet, Hk is the kth order empirical entropy, r is the branching factor of the multi-ary wavelet tree such that 2 ≤ r ≤ √n and r ≤ O(log<SUP>1-ε</SUP>σn), and 0 < ε < 1/2 is a constant.
-
Improving Lookup Time Complexity of Compressed Suffix Arrays using Multi-ary Wavelet Tree
Wu, Zheng,Na, Joong-Chae,Kim, Min-Hwan,Kim, Dong-Kyue Korean Institute of Information Scientists and Eng 2009 Journal of Computing Science and Engineering Vol.3 No.1
In a given text T of size n, we need to search for the information that we are interested. In order to support fast searching, an index must be constructed by preprocessing the text. Suffix array is a kind of index data structure. The compressed suffix array (CSA) is one of the compressed indices based on the regularity of the suffix array, and can be compressed to the $k^{th}$ order empirical entropy. In this paper we improve the lookup time complexity of the compressed suffix array by using the multi-ary wavelet tree at the cost of more space. In our implementation, the lookup time complexity of the compressed suffix array is O(${\log}_{\sigma}^{\varepsilon/(1-{\varepsilon})}\;n\;{\log}_r\;\sigma$), and the space of the compressed suffix array is ${\varepsilon}^{-1}\;nH_k(T)+O(n\;{\log}\;{\log}\;n/{\log}^{\varepsilon}_{\sigma}\;n)$ bits, where a is the size of alphabet, $H_k$ is the kth order empirical entropy r is the branching factor of the multi-ary wavelet tree such that $2{\leq}r{\leq}\sqrt{n}$ and $r{\leq}O({\log}^{1-{\varepsilon}}_{\sigma}\;n)$ and 0 < $\varepsilon$ < 1/2 is a constant.
-
샘플링 비율 조정을 통한 Clark의 Select 함수의 효율적 구현
나중채,심정섭 한국차세대컴퓨팅학회 2009 한국차세대컴퓨팅학회 논문지 Vol.5 No.1
압축 접미사 배열(compressed suffix array)은 생물정보학(bioinformatics)에서 널리 활용되는 색인(index) 자료구조이다. 압축 접미사 배열을 구현하기 위해서는 간결 표현(succinct representation)에 필수적인 비트 문자열에 대한 select 함수가 필요하다. 잘 알려진 Clark의 select 알고리즘은 비트 문자열 내의 1의 비율에 따라서 성능(질의 시간과 필요한 메모리)이 달라진다는 문제점이 있다. 본 논문에서는 1의 비율에 관계없이 성능이 일정한 구현 방법을 제시하고 시뮬레이션을 통해 이를 입증한다. In this paper, we present a novel approach of Context-aware Mobile Augmented Reality (CAMAR)combining context awareness and mobile augmented reality. CAMAR is aware of a user’s context through theuser-centric integration and inference of contextual information in smart space. Based on the user’s context, itfilters the content relevant to the user and overlays the filtered content over the associated physical entities. Inaddition, the CAMAR generates the community according to the relationship between the entities and enables auser to share the personalized content with other mobile users selectively in a customized way. We developethe software platform that supports developers to make CAMAR-enabled applications on the UMPC. To showthe effectiveness of our work, we implemented CAMAR-enabled applications for smart home environmentsand observed the users’feedback to the applications through usability tests. Ultimately, we have confirmed thepotentials for the proposed CAMAR as a personalized AR interface in smart space.
연관 검색어 추천
이 검색어로 많이 본 자료
활용도 높은 자료
