Bagaimanakah kita boleh memisahkan teks bersebelahan dengan cekap kepada senarai perkataan menggunakan pendekatan kebarangkalian?

Memisahkan Teks Bersebelahan menjadi Senarai Perkataan dengan Cekap

Soalan itu menimbulkan cabaran: diberi rentetan teks tanpa ruang, cipta algoritma untuk mengekstrak perkataan individu.

Pendekatan naif akan secara berulang mengenal pasti dan mengalih keluar perkataan terpanjang yang mungkin. Walau bagaimanapun, strategi ini mungkin terbukti tidak cekap dalam senario dunia sebenar.

Pendekatan Kebarangkalian

Untuk mengatasi batasan ini, model kebarangkalian menggabungkan frekuensi perkataan ke dalam algoritma. Undang-undang Zipf menghampiri kebarangkalian perkataan sebagai berkadar songsang dengan kedudukannya dalam kekerapan perkataan.

Menggunakan model ini, kita boleh mentakrifkan fungsi kos untuk setiap pemecahan perkataan yang mungkin sebagai kebarangkalian log negatif bagi keseluruhan ayat jika itu rehat perlu dibuat. Pengaturcaraan dinamik digunakan untuk mencari kata putus dengan jumlah kos terendah.

Pelaksanaan

Kod Python yang disediakan di bawah melaksanakan algoritma ini:

<code class="python">from math import log

# Build a cost dictionary based on Zipf's law
words = open("words-by-frequency.txt").read().split()
maxword = max(len(x) for x in words)
wordcost = dict((k, log((i+1)*log(len(words)))) for i,k in enumerate(words))

def infer_spaces(s):
    cost = [0]
    for i in range(1,len(s)+1):
        candidates = enumerate(reversed(cost[max(0, i-maxword):i]))
        c,k = min((c + wordcost.get(s[i-k-1:i], 9e999), k+1) for k,c in candidates)
        cost.append(c)
    out = []
    i = len(s)
    while i>0:
        c,k = best_match(i)
        assert c == cost[i]
        out.append(s[i-k:i])
        i -= k
    return " ".join(reversed(out))</code>

Menggunakan ini kod:

<code class="python">s = 'thumbgreenappleactiveassignmentweeklymetaphor'
print(infer_spaces(s))</code>

Menghasilkan:

thumb green apple active assignment weekly metaphor

Pengoptimuman

Untuk kecekapan selanjutnya, pokok akhiran boleh dibina daripada senarai perkataan ke mengurangkan ruang carian. Memisahkan rentetan input kepada ketulan yang lebih kecil juga boleh mengurangkan penggunaan memori.

Kesimpulan

Dengan memodelkan kekerapan perkataan dan menggunakan pengaturcaraan dinamik, kami memperoleh algoritma yang cekap untuk memisahkan teks bersebelahan ke dalam perkataan individu, menawarkan hasil yang tepat untuk teks dunia nyata.

Atas ialah kandungan terperinci Bagaimanakah kita boleh memisahkan teks bersebelahan dengan cekap kepada senarai perkataan menggunakan pendekatan kebarangkalian?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!