البحث عن 25000 كلمة داخل النص

Question

أحتاج إلى العثور على تكرارات تصل إلى 25000 كلمة تقريبًا داخل النص.ما هي الخوارزمية/المكتبة الأكثر ملاءمة لهذا الغرض؟

اللغة الهدف هي C++

Answer 1

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

Answer 2

<اقتباس فقرة>   

وأنا استخدم مرة واحدة خوارزمية بوير مور وكان سريع جدا.

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

ويستخدم أيضا stdext::hash_map من STL Dinkumware. يستعاض مع std::tr1::unordered_map أو التنفيذ الملائم.

وهناك تفسيرا من الخوارزمية في <لأ href = "http://www.inf.fu-berlin.de/inst/ag-bio/FILES/ROOT/Teaching/Lectures/SS08//ssa/script -02-HorspoolWuManber.pdf "يختلط =" noreferrer "> النصي محاضرة من محاضرة في جامعة برلين الحرة، التي عقدها كنوت رينرت.

الورقة الأصلية هو أيضا على الانترنت (فقط وجدت أنه مرة أخرى) ولكن أنا لا ' ر سيما مثل شبة الكود قدم هناك.

#ifndef FINDER_HPP
#define FINDER_HPP

#include <string>

namespace thru { namespace matching {

class Finder {
public:
    virtual bool find() = 0;

    virtual std::size_t position() const = 0;

    virtual ~Finder() = 0;

protected:
    static size_t code_from_chr(char c) {
        return static_cast<size_t>(static_cast<unsigned char>(c));
    }
};

inline Finder::~Finder() { }

} } // namespace thru::matching

#endif // !defined(FINDER_HPP)

---

#include <vector>
#include <hash_map>

#include "finder.hpp"

#ifndef WUMANBER_HPP
#define WUMANBER_HPP

namespace thru { namespace matching {

class WuManberFinder : public Finder {
public:

    WuManberFinder(std::string const& text, std::vector<std::string> const& patterns);

    bool find();

    std::size_t position() const;

    std::size_t pattern_index() const;

private:

    template <typename K, typename V>
    struct HashMap {
        typedef stdext::hash_map<K, V> Type;
    };

    typedef HashMap<std::string, std::size_t>::Type shift_type;
    typedef HashMap<std::string, std::vector<std::size_t> >::Type hash_type;

    std::string const& m_text;
    std::vector<std::string> const& m_patterns;
    shift_type m_shift;
    hash_type m_hash;
    std::size_t m_pos;
    std::size_t m_find_pos;
    std::size_t m_find_pattern_index;
    std::size_t m_lmin;
    std::size_t m_lmax;
    std::size_t m_B;
};

} } // namespace thru::matching

#endif // !defined(WUMANBER_HPP)

---

#include <cmath>
#include <iostream>

#include "wumanber.hpp"

using namespace std;

namespace thru { namespace matching {

WuManberFinder::WuManberFinder(string const& text, vector<string> const& patterns)
    : m_text(text)
    , m_patterns(patterns)
    , m_shift()
    , m_hash()
    , m_pos()
    , m_find_pos(0)
    , m_find_pattern_index(0)
    , m_lmin(m_patterns[0].size())
    , m_lmax(m_patterns[0].size())
    , m_B()
{
    for (size_t i = 0; i < m_patterns.size(); ++i) {
        if (m_patterns[i].size() < m_lmin)
            m_lmin = m_patterns[i].size();
        else if (m_patterns[i].size() > m_lmax)
            m_lmax = m_patterns[i].size();
    }

    m_pos = m_lmin;
    m_B = static_cast<size_t>(ceil(log(2.0 * m_lmin * m_patterns.size()) / log(256.0)));

    for (size_t i = 0; i < m_patterns.size(); ++i)
        m_hash[m_patterns[i].substr(m_patterns[i].size() - m_B)].push_back(i);

    for (size_t i = 0; i < m_patterns.size(); ++i) {
        for (size_t j = 0; j < m_patterns[i].size() - m_B + 1; ++j) {
            string bgram = m_patterns[i].substr(j, m_B);
            size_t pos = m_patterns[i].size() - j - m_B;

            shift_type::iterator old = m_shift.find(bgram);
            if (old == m_shift.end())
                m_shift[bgram] = pos;
            else
                old->second = min(old->second, pos);
        }
    }
}

bool WuManberFinder::find() {
    while (m_pos <= m_text.size()) {
        string bgram = m_text.substr(m_pos - m_B, m_B);
        shift_type::iterator i = m_shift.find(bgram);
        if (i == m_shift.end())
            m_pos += m_lmin - m_B + 1;
        else {
            if (i->second == 0) {
                vector<size_t>& list = m_hash[bgram];
                // Verify all patterns in list against the text.
                ++m_pos;
                for (size_t j = 0; j < list.size(); ++j) {
                    string const& str = m_patterns[list[j]];
                    m_find_pos = m_pos - str.size() - 1;
                    size_t k = 0;

                    for (; k < str.size(); ++k)
                        if (str[k] != m_text[m_find_pos + k])
                            break;

                    if (k == str.size()) {
                        m_find_pattern_index = list[j];
                        return true;
                    }
                }
            }
            else
                m_pos += i->second;
        }
    }

    return false;
}

size_t WuManberFinder::position() const {
    return m_find_pos;
}

size_t WuManberFinder::pattern_index() const {
    return m_find_pattern_index;
}

} } // namespace thru::matching

مثال على الاستخدام:

vector<string> patterns;
patterns.push_back("announce");
patterns.push_back("annual");
patterns.push_back("annually");

WuManberFinder wmf("CPM_annual_conference_announce", patterns);

while (wmf.find())
    cout << "Pattern \"" << patterns[wmf.pattern_index()] <<
        "\" found at position " << wmf.position() << endl;

Answer 3

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

ومن مساحة للغاية كفاءة، أفضل بكثير من مجرد تجزئة كل كلمة: مع معدل إيجابية كاذبة 1٪ يجب أن لا تتطلب سوى 9.6 بت لكل عنصر. يتم خفض معدل إيجابية كاذبة من قبل عامل من 10 لكل 4.8 بت إضافية لكل عنصر. على النقيض من ذلك إلى تجزئة واضحة، الأمر الذي يتطلب عادة sizeof (دولي) == 32 بت لكل عنصر.

ولدي التنفيذ في C # هنا: http://www.codeplex.com/bloomfilter

وهنا مثال، مما يدل على استخدامه مع سلاسل:

int capacity = 2000000; // the number of items you expect to add to the filter
Filter<string> filter = new Filter<string>(capacity);
filter.Add("Lorem");
filter.Add("Ipsum");
if (filter.Contains("Lorem"))
    Console.WriteLine("Match!");

Answer 4

وإذا كان جسم كبير جدا، في محاولة لتحسين ذلك بهذه الطريقة:

وحساب البعثرة من كل كلمة تحتاج إلى التحقق، وتكليف كل شار على عدد أولي عدد صحيح وثم ضرب كل رقم معا، تخزين كل كلمة number-> في multimap (تحتاج إلى السماح لقيمة متعددة على مفتاح واحد)

وحين مسح قائمة الكلمات، حساب تجزئة في نفس الطريق لكل كلمة، ثم الحصول على كلمة (ق) المرتبطة مفتاح المحسوبة على hashmap. استخدام الأعداد الصحيحة كمفتاح، لديك استرجاع O (1)؛ بهذه الطريقة يمكن أن تجد في وسيلة سريعة حقا إذا كانت الكلمة المصنعة لديها بعض الجناس الناقص (أنت تضرب حرفا) داخل الخريطة.

وتذكر: يمكنك تخزين في multimap مجموعة كلمة لها أن نفس التجزئة، لذلك تحتاج الآن إلى العثور على تطابق في هذه المجموعة تقلص إلى حد كبير. كنت بحاجة إلى هذا الاختيار إضافية عن وجود ببساطة عدد صحيح على خريطة لا يعني وجود كلمة في المجموعة المرتبطة بها: نحن نستخدم تجزئة هنا لتقليل المساحة الحسابي لهذه المشكلة، ولكن هذا يدخل الاصطدام التي تحتاج إلى أن disambiguated التدقيق على كل الجناس الناقص التي تم تحديدها.

Answer 5

واستخدم أهو-Corasick خوارزمية . وهي مصنوعة لهذا التطبيق. ستحتاج فقط لقراءة كل حرف في نص البحث مرة واحدة. لقد نفذت مؤخرا واستخدامه مع نتائج عظيمة.

Answer 6

وكما يقول خافيير، وأبسط حل هو على الارجح جدول تجزئة.

في C ++، وهذا يمكن تنفيذها باستخدام مجموعة STL. أولا إضافة عبارة اختبار 25،000 إلى مجموعة، ثم مسح من خلال كل كلمة في النص، وذلك باستخدام set.find (current_word) لتقييم ما إذا كانت الكلمة بين الكلمات اختبار 25000.

وset.find سريع لوغاريتمي، لذلك ينبغي الكلمات 25،000 الاختبار لن تكون كبيرة جدا. ومن الواضح أن خوارزمية خطية في عدد من الكلمات في النص.

Answer 7

وإذا كان النص الذي تبحث ضخم، ثم قد يكون من المفيد القيام ببعض تجهيزها: تجميع الخاص بك 25،000 الكلمات في TRIE

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

إذا نص الخاص بك كبير مجرد (وليس ضخمة)، ثم ببساطة تبحث عن كل كلمة في جدول تجزئة وربما يكفي.

Answer 8

يقول نائب بيرج:

لقد استخدمت مرة واحدة خوارزمية بوير موري وكان سريعًا جدًا.

مع Boyer-Moore، ألا تبحث عادةً عن كتلة نصية؟ أعزب خيط؟

للحصول على حل سهل التنفيذ، اتبع نهج جدول التجزئة الذي اقترحه Javier.مرشح Bloom الذي اقترحه FatCat1111 يجب أن يعمل أيضًا...اعتمادا على الأهداف.

Answer 9

قد يكون تخزين dictionnary الأولي (الكلمات 25000) في جدول بيركلي ديسيبل تجزئة على القرص، والتي يمكنك على الأرجح استخدام مباشرة من C / C ++ (أنا أعلم أنك تستطيع أن تفعل ذلك من بيرل)، ولكل كلمة في النص، الاستعلام إذا كان موجودا في قاعدة البيانات.

Answer 10

ويمكنك أيضا فرز النص والنصوص القائمة حسب الترتيب الأبجدي. عندما يكون لديك اثنين من مرتبة arraysyou يمكن بسهولة العثور على المباريات في الزمن الخطي.

Answer 11

وأنت تريد ترناري البحث شجرة . ويمكن الاطلاع على التنفيذ الجيد هنا .

Answer 12

وبنيت أهو-Corasick خوارزمية خصيصا لهذا الغرض: البحث عن كلمات كثيرة في وقت واحد