کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
429067 687030 2010 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On building minimal automaton for subset matching queries
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On building minimal automaton for subset matching queries
چکیده انگلیسی

We address the problem of building an index for a set D of n strings, where each string location is a subset of some finite integer alphabet of size σ, so that we can answer efficiently if a given simple query string (where each string location is a single symbol) p   occurs in the set. That is, we need to efficiently find a string d∈Dd∈D such that p[i]∈d[i]p[i]∈d[i] for every i  . We show how to build such index in O(nlogσ/Δ(σ)log(n))O(nlogσ/Δ(σ)log(n)) average time, where Δ is the average size of the subsets. Our methods have applications e.g. in computational biology (haplotype inference) and music information retrieval.

Research highlights
► Space-efficient dictionary representation for strings of alphabet subsets.
► Algorithm for directly building pseudo-minimal DFA for subset matching.
► Efficient DFA minimization via pseudo-minimization.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 110, Issue 24, 30 November 2010, Pages 1093–1098
نویسندگان
,