آرایه ال‌سی‌پی

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

در علوم رایانه، آرایه بلندترین پیشوند مشترک (آرایه ال‌سی‌پی) (به انگلیسی: LCP array) یک داده‌ساختار کمکی برای آرایه پسوندی است. در این آرایه، طولانی‌ترین پیشوند مشترک بین هر دو پسوند متوالی موجود در آرایه پسوندی ذخیره می‌شود.

تاریخچه

آرایه ال‌سی‌پی توسط Udi Manber و Gene Myers در سال ۱۹۹۰ به همراه آرایه پسوندی و برای بهبود سرعت الگوریتم جستجوی الگو در متن ارائه شد.^[۱]

تعریف

فرض کنیم $A$ آرایه پسوندی رشته $S=S[1]S[2]...S[n]$ بوده و $lcp(v,w)$ نشان‌دهندهٔ طولانی‌ترین پیشوند مشترک رشته‌های $v$ و $w$ باشد. هم چنین زیررشتهٔ $S$ از حرف $i$ ام تا حرف $j$ ام را با $S[i,j]$ نشان می‌دهیم. در این صورت آرایه ال‌سی‌پی $H[1,n]$ یک آرایه با اندازهٔ $n$ از اعداد صحیح است که $H[1]$ تعریف نشده‌است و $H[i]=lcp(S[A[i-1],n],S[A[i],n])$ به ازای هر $1<i\leq n$ . با توجه به اینکه $A[i]$ نشان‌دهندهٔ جایگاه شروع $i$ امین کوچک‌ترین پسوند رشتهٔ $S$ از نظر لغتنامه‌ای است، پس $H[i]$ طول بلندترین پیشوند مشترک $i-1$ امین و $i$ امین پسوند رشتهٔ $S$ از نظر لغتنامه‌ای است ( $1<i\leq n$ ).

مثال

رشتهٔ $S=banana\$$ را در نظر بگیرید:

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

و آرایهٔ پسوندی مرتب‌شدهٔ متناظر با آن:

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

پسوندهای رشتهٔ $S$ که به صورت ستونی و مرتب‌شده نوشته شده‌اند:

i	۱	۲	۳	۴	۵	۶	۷
A[i]	۷	۶	۴	۲	۱	۵	۳
1	$	a	a	a	b	n	n
2		$	n	n	a	a	a
3			a	a	n	$	n
4			$	n	a		a
5				a	n		$
6				$	a
7					$

آرایهٔ ال‌سی‌پی با مقایسهٔ پسوندهای متوالی از نظر لغت‌نامه‌ای برای مشخص کردن بزرگ‌ترین پیشوند مشترک آن‌ها محاسبه می‌شود:

i	۱	۲	۳	۴	۵	۶	۷
H[i]	⊥	۰	۱	۳	۰	۰	۲

برای مثال، $H[4]=3$ طول بزرگ‌ترین پیشوند مشترک بین $S[A[3],7]=S[4,7]=ana\$$ و $S[A[4],7]=S[2,7]=anana\$$ یعنی رشته $ana$ است.

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

فرض کنید می‌خواهیم تعداد رخدادهای یک الگوی $P$ (به طول $m$ ) در یک متن $T$ (به طول $N$ ) را بیابیم. می‌توان با دو بار استفاده از جستجوی دودویی، مکان اولین و آخرین رخداد $P$ در آرایه پسوندی $T$ را بدست آورد و در نتیجه تعداد رخدادهای رشته $P$ در متن $T$ بدست می‌آید. در هر کدام از جستجوهای دودویی $O(logN)$ مقایسه نیاز است و با توجه به اینکه در هر مقایسه رشتهٔ $P$ را با یکی از عناصر آرایه پسوندی مقایسه می‌کنیم، در بدترین حالت ممکن است نیاز به مقایسهٔ کامل دو رشته باشد که به معنی مقایسهٔ $m$ کاراکتر است؛ بنابراین زمان اجرای این الگوریتم از $O(m\times logN)$ است.

با استفاده از آرایه ال‌سی‌پی، الگوریتمی با زمان اجرای $O(m+logN)$ ارائه می‌دهیم.^[۱] به ازای هر $1\leq i\leq n$ ، $S_{i}$ را برابر $S[A[i],n]$ تعریف می‌کنیم؛ در واقع $S_{i}$ برابر $i$ امین کوچک‌ترین پسوند $S$ است. ابتدا فرض کنیم به ازای هر $1\leq i,j\leq n$ مقدار $lcp(S_{i},S_{j})$ از قبل محاسبه شده‌است. در هر مرحله از جستجوی دودویی، یک بازه $(L,...,R)$ در آرایه پسوندی به همراه نقطه میانی آن $M$ را در نظر می‌گیریم. سپس با مقایسهٔ $P$ و $S_{M}$ مشخص می‌کنیم که جستجو را در بازهٔ $(L,...,M)$ ادامه دهیم یا بازهٔ $(M,...,R)$ . فرض کنیم $P$ بزرگتر از $S_{M}$ باشد و اولین حرفی از $P$ و $S_{M}$ که متفاوت اند حرف $k+1$ ام باشد؛ یعنی $lcp(P,S_{M})=k$ . پس در مرحلهٔ بعدی جستجو، بازه $(M,...,R)$ با نقطه میانی $M'$ را در نظر می‌گیریم. با توجه به فرضی که کردیم، مقدار $lcp(S_{M},S_{M'})=k'$ از قبل محاسبه شده‌است و در زمان $O(1)$ قابل دسترس است. سه حالت ممکن است پیش بیاید:

حالت ۱: $k<k'$ ، یعنی طولانی‌ترین پیشوند مشترک $P$ و $S_{M}$ کمتر از طولانی‌ترین پیشوند مشترک $S_{M}$ و $S_{M'}$ است؛ بنابراین $k+1$ امین حرف $S_{M}$ و $S_{M'}$ یکسان است و چون $P>S_{M}$ در نتیجه $P>S_{M'}$ . بنابراین جستجو را در بازهٔ $(M',...,R)$ ادامه می‌دهیم.
حالت ۲: $k>k'$ ، یعنی $P$ و $S_{M}$ پیشوند مشترک بیشتری نسبت به $S_{M}$ و $S_{M'}$ دارند. با توجه به اینکه آرایه پسوندی با ترتیب لغت‌نامه‌ای مرتب شده‌است، پس $S_{M'}>S_{M}$ . از آنجا که اولین حرفی که $S_{M}$ و $S_{M'}$ در آن متفاوت اند حرف $k'+1$ ام است و رشته‌های $P$ و $S_{M}$ در این حرف یکسان اند، پس $S_{M'}>P$ و در نتیجه جستجو در بازه $(M,...,M')$ ادامه می‌یابد.
حالت ۳: $k=k'$ ، یعنی رشته‌های $S_{M}$ و $S_{M'}$ در $k$ حرف اول با رشتهٔ $P$ یکسان اند. برای مقایسه رشته‌های $S_{M'}$ و $P$ ، این دو رشته را از حرف $k+1$ ام به بعد مقایسه می‌کنیم تا به اولین حرف متفاوت برسیم. به این ترتیب در مرحلهٔ بعدی الگوریتم جستجوی دودویی، مقدار $lcp(P,S_{M'})$ را داریم و می‌توانیم به همین صورت الگوریتم جستجوی $P$ را ادامه دهیم.

در الگوریتم بالا هر کاراکتر از رشتهٔ $P$ حداکثر یک بار با کاراکترهای متن $T$ مقایسه می‌شود؛ بنابراین زمان اجرای این الگوریتم $O(m+logN)$ است.

اما فرض کرده بودیم به ازای هر $1\leq i,j\leq n$ مقدار $lcp(S_{i},S_{j})$ از قبل محاسبه شده‌است. توجه کنیم که همهٔ بازه‌های ممکن $(L,...,R)$ در الگوریتم جستجوی دودویی ظاهر نمی‌شوند. به ازای هر نقطهٔ $2\leq M\leq n-1$ ، دقیقاً یک بازه با نقطهٔ میانی $M$ وجود دارد که در الگوریتم جستجوی دودویی ممکن است ظاهر شود. این بازه را با $(L_{M},M,R_{M})$ نشان می‌دهیم و به ازای هر $2\leq M\leq n-1$ تعریف می‌کنیم:

$Llcp[M]=lcp(S_{L_{M}},S_{M})$
$Rlcp[M]=lcp(S_{M},S_{R_{M}})$

با توجه به الگوریتم گفته شده، فقط به مقادیر آرایه‌های $Llcp$ و $Rlcp$ نیاز داریم که حافظه‌ای از $O(N)$ اشغال می‌کنند. هم‌چنین از روی آرایه ال‌سی‌پی و در زمان $O(N)$ می‌توان مقادیر $Llcp$ و $Rlcp$ را محاسبه کرد.

ساختن آرایه ال‌سی‌پی

در سال ۱۹۹۰ Manber و Myers الگوریتمی از $O(NlogN)$ دادند که در کنار آرایه پسوندی، آرایه ال‌سی‌پی را نیز محاسبه می‌کند.^[۱] در سال ۲۰۰۳ الگوریتمی از $O(N)$ برای ساختن هم‌زمان آرایه پسوندی و آرایه ال‌سی‌پی ارایه شد.^[۲]

در سال ۲۰۰۱ الگوریتمی ارایه شد که در $O(N)$ آرایه ال‌سی‌پی را از روی متن و آرایه پسوندی محاسبه می‌کند.^[۳]

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

منابع

↑ ^۱٫۰ ^۱٫۱ ^۱٫۲ Manber, Udi; Myers, Gene (1990). Suffix arrays: a new method for on-line string searches. First Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 319–327.
↑ Kärkkäinen, Juha; Sanders, Peter (2003). Simple linear work suffix array construction. Proceedings of the 30th international conference on Automata, languages and programming. pp. 943–955. Retrieved 2012-08-28.
↑ Kasai, T.; Lee, G.; Arimura, H.; Arikawa, S.; Park, K. (2001). Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications. Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science. Vol. 2089. pp. 181–192. doi:10.1007/3-540-48194-X_17. ISBN 978-3-540-42271-6.

[one-1] ۱٫۰ ^۱٫۱ ^۱٫۲ Manber, Udi; Myers, Gene (1990). Suffix arrays: a new method for on-line string searches. First Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 319–327.

[two-2] Kärkkäinen, Juha; Sanders, Peter (2003). Simple linear work suffix array construction. Proceedings of the 30th international conference on Automata, languages and programming. pp. 943–955. Retrieved 2012-08-28.

[three-3] Kasai, T.; Lee, G.; Arimura, H.; Arikawa, S.; Park, K. (2001). Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications. Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science. Vol. 2089. pp. 181–192. doi:10.1007/3-540-48194-X_17. ISBN 978-3-540-42271-6.

[۱]

[۲]

[۳]