ماشین غیرمدور قطعی متناهی

The strings "tap", "taps", "top", and "tops" stored in a درخت پیشوندی (left) and a DAFSA (right), EOW stands for End-of-word.

در علوم رایانه، یک ماشین غیر مدور قطعی متناهی، (DAFSA)، یا یک گراف جهت‌دار بدون دور از کلمات(DAWG، هر چند که این نام به ساختمان داده مربوط به توابع به عنوان شاخص پسوند هم اشاره می‌کند) یک ساختارداده است که نشان دهنده مجموعه‌ای از رشته هاست، و اجازه می‌دهد تا برای یک عملیات پرس و جو که امتحان کند که آیا یک رشته داده شده متعلق به مجموعه در زمان متناسب با طول آن هست یا نه. از این جهات، DAFSA بسیار شبیه به یک درخت پیشوندی است، اما با فضای بسیار کارآمد ترو به صرفه تر.

DAFSA یک مورد خاص از یک تشخیص دهنده متناهی است که شبیه به شکل یک گراف بدون دور جهت دار با یک راس مبدأ (یک راس با لبه‌های ورودی)، که در آن هر لبه گراف توسط یک نام یا نماد برچسب خورده است، که در آن هر راس حداکثر یک لبه خروجی برای هر حرف یا نماد را داراست. رشته‌های ارائه شده توسط DAFSA از راس مبدأ به هر راس سینک یا مقصد (یک راس با هیچ لبه خروجی) با نمادهای مشخص شده بر روی هر مسیر در گراف مشخص می‌شوند. در واقع، یک ماشین قطعی متناهی بدون دور است اگر و تنها اگر آن را یک مجموعه متناهی از رشته به رسمیت می‌شناسد.

مقایسه با درخت پیشوندی با فرض اینکه برای رسیدن به یک راس چند مسیر متفاوت وجود داشته باشد، DAFSA ممکن است به‌طور قابل توجهی راس کمتر از درخت پیشوندی مرتبط برای رسیدن به راس مقصد استفاده کند. به عنوان مثال، برای چهار کلمه انگلیسی "tap", "taps", "top", and "tops". یک درخت پیشوندی با ۱۱ راس وجود خواهد داشت، یکی برای هر رشته به عنوان یک پیشوند برای این کلمات، یا برای هر کلمه " پایان رشته " برچسب خورده باشد. با این حال، DAFSA می‌تواند این چهار کلمهٔ مشابه را با استفاده از تنها شش راس vi برای i از ۰ تا ۵، و لبه‌های زیر نشان دهد:

یک لبه از V0 به V1 با برچسب "T"، دو لبه از V1 تا V2 با برچسب "A" و " O "، یک لبه از V2 به V3 با برچسب" p "، یک لبه از V3به V4 با برچسب" S "، و لبه‌هایی از V3 و V4 به V5 با برچسب " پایان رشته ". یک مقایسه بین حافظه و قابلیت وجود دارد، زیرا یک DAFSA استاندارد می‌تواند بگوید که یک کلمه در آن وجود دارد یا نه، اما نمی‌توانداطلاعات اضافه‌ای در مورد آن بدهد، در حالی که یک درخت پیشوندی چنین قابلیتی را داراست.

تفاوت اصلی بین DAFSA و درخت پیشوندی حذف افزونگی پسوند و میانوند در ذخیره‌سازی رشته است. درخت پیشوندی به حذف افزونگی پیشوند از همه پیشوندها مشترک بین رشته‌ها می‌پردازد، مانند پزشکان و دکترای که پیشوند دکتر مشترک است. در یک DAFSA پسوند مشترک نیز به اشتراک گذاشته می‌شود، برای کلماتی که مجموعه‌ای از پسوندهای یکسان برای دیگر دارند. برای مجموعه فرهنگ لغت از کلمات انگلیسی رایج، این روش، باعث کاهش استفاده ازحافظه در هنگام ترجمه می‌شود.

از آنجا که می‌توان با چندین مسیر به یک گره پایانی در DAFSAرسید ،DAFSA به‌طور مستقیم نمی‌تواند اطلاعات کمکی و اضافی مربوط به هر مسیر را ذخیره کند، به عنوان مثال تکرار یک کلمه در زبان انگلیسی. با این حال، اگر برای هر گره ما تعداد مسیرهای منحصر به فرد از طریق آن نقطه در ساختار را ذخیره کنیم، می‌توانیم آن را به بازیابی شاخص از یک کلمه، یا یک کلمه با توجه به شاخص آن استفاده کنید. در آن صورت اطلاعات کمکی می‌تواند در یک آرایه ذخیره می‌شود.

منابع

    • Blumer, A.; Blumer, J.; Haussler, D.; Ehrenfeucht, A.; Chen, M.T.; Seiferas, J. (1985), "The smallest automation recognizing the subwords of a text", Theoretical computer science, 40: 31–55, doi:10.1016/0304-3975(85)90157-4
    • Appel, Andrew; Jacobsen, Guy (1988), "The World's Fastest Scrabble Program" (PDF), Communications of the ACM. One of the early mentions of the data structure.
    • Jansen, Cees J. A.; Boekee, Dick E. (1990), "On the significance of the directed acyclic word graph in cryptology", Advances in Cryptology — AUSCRYPT '90, Lecture Notes in Computer Science, vol. 453, Springer Science+Business Media, pp. 318–326, doi:10.1007/BFb0030372, ISBN 3-540-53000-2.
    • Epifanio, Chiara; Mignosi, Filippo; Shallit, Jeffrey; Venturini, Ilaria (2004), "Sturmian graphs and a conjecture of Moser", in Calude, Cristian S.; Calude, Elena; Dineen, Michael J. (eds.), Developments in language theory. Proceedings, 8th international conference (DLT 2004), Auckland, New Zealand, December 2004, Lecture Notes in Computer Science, vol. 3340, Springer Science+Business Media, pp. 175–187, ISBN 3-540-24014-4, Zbl 1117٫68454 {{citation}}: Check |zbl= value (help)

    پیوند به بیرون

    This article is issued from ویکی‌پدیا. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.