آرایه پسوندی

آرایهٔ پسوندی
نوع	آرایه
اختراع شده توسط	(Manber و Myers 1990)
زمان اجرای الگوریتم; در نماد O بزرگ

در علوم رایانه یک آرایهٔ پسوندی آرایه‌ای مرتب‌شده از همهٔ پسوندهای یک رشته است. این داده ساختار در الگوریتم‌های فشرده سازی و بیوانفورماتیک کاربرد دارد.

آرایهٔ پسوندی در سال ۱۹۹۰ توسط (Manber و Myers 1990) به‌عنوان جایگزینی ساده‌تر و همچنین از نظر حافظه بهینه تر برای درخت پسوندی معرفی شد. همچنین در سال ۱۹۸۷ به طور مستقل توسط Gaston Gonnet با نام PAT کشف شده بود.

تعریف

اگر رشتهٔ $S=S[1]S[2]...S[n]$

را داشته باشیم،

S[i,j]

را زیر رشتهٔ آن از حرف

i

ام تا حرف

j

ام تعریف می‌کنیم.

آرایهٔ پسوندی $A$

برای رشتهٔ

S

یک آرایه از اعداد طبیعی است به طوری که خانه‌های آن نشان دهندهٔ نقاط شروع پسوندهای

S

به ترتیب الفبایی است، یعنی در خانهٔ

A[i]

نقطهٔ شروع

i

امین کوچکترین پسوند رشتهٔ

S

قرار دارد. پس برای همهٔ

1<i\leq n

داریم:

S[A[i-1],n]<S[A[i],n]

مثال

اگر داشته باشیم$banana $S=$

:

i	۱	۲	۳	۴	۵	۶	۷
$S[i]$	b	a	n	a	n	a	$

در انتهای رشته یک حرف $ اضافه می‌کنیم که از نظر الفبایی کوچکترین حرف الفباست.

پسوندهای رشته به شرح زیر است:

Suffix	i
$banana	۱
$anana	۲
$nana	۳
$ana	۴
$na	۵
$a	۶
$	۷

پسوندها را به ترتیب الفبایی و به صورت نزولی مرتب می‌کنیم:

Suffix	i
$	۷
$a	۶
$ana	۴
$anana	۲
$banana	۱
$na	۵
$nana	۳

آرایهٔ پسوندی $A$

شامل نقطهٔ شروع پسوندهای مرتب شده:

i	۱	۲	۳	۴	۵	۶	۷
$A[i]$	۷	۶	۴	۲	۱	۵	۳

اگر در آرایهٔ پسوندی پسوندهای هر عدد را به صورت عمودی زیر آن بنویسیم بدین شکل خواهد بود:

i	۱	۲	۳	۴	۵	۶	۷
$A[i]$	۷	۶	۴	۲	۱	۵	۳
۱	$	a	a	a	b	n	n
۲		$	n	n	a	a	a
۳			a	a	n	$	n
۴			$	n	a		a
۵				a	n		$
۶				$	a
۷					$

برای مثال، $A[3]$

برابر است با ۴ و نشان دهندهٔ ۴ امین پسوند در ترتیب الفبایی بین پسوندهای رشتهٔ

S

است که می‌شود $ana .

ارتباط به درخت پسوندی

آرایهٔ پسوندی ارتباط نزدیکی با درخت پسوندی دارند:

آرایه‌ی پسوندی را می‌توان با یک جستجو اول عمق بر روی درخت پسوندی ‌ساخت.
درخت پسوندی را می‌توان در زمان خطی با استفاده از ترکیبی از آرایهٔ پسوندی و آرایهٔ LCP ساخت.

و همچنین نشان داده شده است که هر الگوریتم درخت پسوندی را می‌توان با یک الگوریتم که از آرایهٔ پسوندی تغییر یافته (برای مثال با استفاده از آرایهٔ LCP) استفاده کند جایگزین کرد به طوری که همان مسئله را در همان پیچیدگی زمانی حل کند.

بهینگی حافظه

آرایهٔ پسوندی برای پیشرفت در بهینگی حافظه نسبت به درخت پسوندی معرفی شد: آرایه‌های پسوندی $n$

عدد صحیح ذخیره می‌کنند و اگر فرض کنیم برای ذخیرهٔ هر عدد صحیح به

4

بایت نیاز داریم، یک آرایهٔ پسوندید در کل به

4n

بایت حافظه نیاز خواهد داشت، که بسیار کمتر از

20n

ای است که برای ذخیرهٔ درخت پسوندی نیاز است.

با این حال در بعضی از کاربردها میزان حافظهٔ مورد نیاز برای آرایهٔ پسوندی می‌تواند هزینه بر باشد. درحالت کلی آرایهٔ پسوندی به ${\mathcal {O}}(n\log n)$

بیت حافظه نیاز دارد، در حالی که متن اصلی با الفبای

\sigma

حرفی فقط به

{\mathcal {O}}(n\log \sigma )

بیت حافظه نیاز دارد. برای مثال در ژنوم انسان که

\sigma =4

و

n=3.4\times 10^{9}

آرایهٔ پسوندی ژنوم به حافظه‌ای نزدیک به

16

برابر حافظهٔ مورد نیاز برای خود ژنوم نیاز دارد.

الگوریتم ساخت

یک درخت پسوندی را می‌توان در ${\mathcal {O}}(n)$

ساخت و با اجرای یک جستجو اول عمق در

{\mathcal {O}}(n)

به آرایهٔ پسوندی تبدیل کرد. پس الگوریتم‌هایی وجود دارند که می‌توانند آرایهٔ پسوندی را در زمان

{\mathcal {O}}(n)

بسازند.

راه حل سادهٔ ساخت آرایه‌های پسوندی استفاده از الگوریتم‌های مرتب‌سازی مقایسه‌ای است، این الگوریتم‌ها به ${\mathcal {O}}(n\log n)$

مقایسه نیاز دارد و با توجه به این که هر مقایسهٔ رشته‌ای به

{\mathcal {O}}(n)

زمان نیاز دارد، کل الگوریتم ساخت آرایهٔ پسوندی با این روش به

{\mathcal {O}}(n^{2}\log n)

زمان نیاز خواهد داشت.

و الگوریتم‌های پیشرفته‌تر با استفاده از این موضوع که رشته‌هایی که باید مرتب شوند، رشته‌های دلخواهی نیستند و به هم ارتباط دارند روش‌هایی با زمان $\Theta (n)$

معرفی می‌کنند.

کاربردها

از آرایهٔ پسوندی می‌توان برای پیدا کردن سریع همهٔ تکرارهای یک رشتهٔ $P$

درون رشتهٔ

S

استفاده کرد. پیدا کردن همهٔ تکرارهای یک رشته

P

هم‌ارز است با پیدا کردن همهٔ پسوندهایی که با

P

شروع می‌شوند.

با توجه به ترتیب الفبایی پسوندها در آرایهٔ پسوندی این پسوندها پشت سر هم قرار گرفته‌اند و می‌توان آن‌ها را به راحتی با استفاده از ۲ بار اجرای جستجوی دودویی پیدا کرد. جستجوی اول نقطهٔ شروع بازه را پیدا می‌کند و جستجوی دوم نقطهٔ پایانی را مشخص می‌کند:

    def search(P):
        l = 0; r = n
        while l < r:
            mid = (l+r) / 2
            if P > suffixAt(A[mid]):
                l = mid + 1
            else:
                r = mid
        s = l; r = n
        while l < r:
            mid = (l+r) / 2
            if P < suffixAt(A[mid]):
                r = mid
            else:
                l = mid + 1
        return (s, r)

با توجه به این که هر پسوند نیاز به مقایسهٔ $m$

کارکتر دارد، پیدا کردن زیررشتهٔ

P

به طول

m

در رشتهٔ

S

به طول

n

در زمان

{\mathcal {O}}(m\log n)

انجام می‌شود.

و این الگوریتم را می‌توان با استفاده از آرایهٔ LCP به ${\mathcal {O}}(m+\log n)$

بهبود بخشید.

منابع

↑ Abouelhoda, Kurtz & Ohlebusch 2002.
↑ Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2002). The Enhanced Suffix Array and Its Applications to Genome Analysis. Algorithms in Bioinformatics. Lecture Notes in Computer Science. 2452. p. 449. doi:10.1007/3-540-45784-4_35.

Manber, Udi; Myers, Gene (1993). "Suffix arrays: a new method for on-line string searches". SIAM Journal on Computing. 22: 935–948. doi:10.1137/0222058.
"Replacing suffix trees with enhanced suffix arrays". Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2004).

جستارهای وابسته

[FOOTNOTEAbouelhodaKurtzOhlebusch2002-1] Abouelhoda, Kurtz & Ohlebusch 2002.

[2] Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2002). The Enhanced Suffix Array and Its Applications to Genome Analysis. Algorithms in Bioinformatics. Lecture Notes in Computer Science. 2452. p. 449. doi:10.1007/3-540-45784-4_35.