string - شرح - table data structure




كيفية العثور على الكلمات من كلمات سارعت (2)

ربما شيء مثل:

http://en.wikipedia.org/wiki/Rabin-Karp_algorithm

والتي هي مشابهة جدا لفكرة التجزئة والمتعلقة خوارزمية آهو-كوراسيك

أحاول العثور على طريقة للعثور على كلمات محددة في النص المخفوق التي تظهر على التوالي. الأحرف التي لم يتم العثور عليها سيكون لها X في المكان.

على سبيل المثال دعونا نقول قائمة من الكلمات القاموس هي:

jane
john
brownbag
foo
youth

والنص المخفوق:

ofozlhuoyt => fooXXyouth
yuawbnrobgajen => XXbrownbagjane
janjeohn => (nothing since jane and john aren't consecutive)

النهج الذي أحاوله:

أقول، لدي التجزئة مع مفاتيح a خلال z مع تعيين القيم لكل مفتاح. كل رقم في المجموعة سيمثل المؤشر حيث الكلمة التي تحتوي على حرف معين.

من المثال أعلاه:

{a: [0,2]}
{b: [2]}
{c: []}
{e: [0]}
{f: [3]}
{g: [2]}
{h: [1,4]}
{j: [0,1]}
...
{n: [0,1,2]}
{o: [1,2,3,4]}
{r: [2]}
{u: [4]}
{t: [4]}
{w: [2]}
{y: [4]}
...
{z: []} 

بعد إعداد ما سبق، يمكننا أن نبدأ النظر في كل حرف من النص مخلوط:

السلسلة الأولى: ofozlhuoyt

  1. o => موجود في 1 و 2 و 3 و 4

  2. تبدأ مع 1: جين (طول 4)

  3. الحصول على 4 حرف: ofoz

  4. "jane".sort(false) == "ofoz".sort(false)?

  5. إذا كاذبة: كرر الخطوات من 1 إلى 3 ل 2 (جون)

  6. إذا كان صحيحا: إضافة فو إلى قائمة من الكلمات الجيدة وبدء الخطوة 0 مع z

هل هناك طريقة أفضل للقيام بذلك؟ أشعر بنية بيانات أفضل موجودة لحل شيء من هذا القبيل ولكن لا أستطيع معرفة ما لاستخدام ..


هناك طريقة أسرع محتملة، شريطة أن يكون لديك ذاكرة كافية لتنفيذها.

أولا، توليد كل التباديل لكل كلمة. لذلك ل "جين" سيكون لديك:

aejn
aenj
ajen
ajne
anej
anje
etc.

ثم، بناء آلة الدولة لخوارزمية أهو-كوراسيك ، مع كل من التباديل لكلمة واحدة الذهاب إلى نفس الحالة النهائية. ستؤدي هذه الحالة النهائية إلى إخراج السلسلة التي تبحث عنها.

الآن تشغيل النص من خلال آلة الدولة. والنتيجة هي الكلمات التي يتم العثور عليها، ومواقفها. يمكنك بعد ذلك فرز الكلمات وجدت حسب الموقف وتحديد ما إذا كانت تظهر على التوالي.

آلة الدولة من المحتمل أن تكون كبيرة جدا (n. الدول لكل كلمة، حيث n هو عدد الأحرف في الكلمة)، وسوف يستغرق بعض الوقت لبناء. ولكن بمجرد أن يبنى، فإنه يطابق بسرعة كبيرة. إذا كانت قائمة الكلمات الخاصة بك ثابتة وكان لديك الكثير من النص للبحث، وهذا هو الطريق للذهاب. شريطة أن يكون لديك ما يكفي من الذاكرة.

لقد استخدمت خوارزمية أهو-كوراسيك المعدلة التي كانت تبحث عن نص لحوادث الملايين من العبارات (الفرقة وأسماء الأغاني) في عناوين الفيديو. احتلت آلة الدولة حوالي 10 غيغابايت من ذاكرة الوصول العشوائي واستغرق حوالي ساعة لبناء، ولكن كان سريعا عندما يتعلق الأمر مطابقة.





tree