Bagaimanakah kita boleh memisahkan rentetan teks perkataan bercantum tanpa ruang kepada perkataan individu dengan cekap?

Memisahkan Teks menjadi Senarai Perkataan Tanpa Ruang

Masalah

Diberi rentetan teks yang terdiri daripada perkataan bercantum tanpa ruang:

Input: "tableapplechairtablecupboard..."

Bagaimanakah kita boleh membahagikan teks ini dengan cekap kepada senarai perkataan individu?

Output: ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], ...]

Algoritma

Pendekatan mudah ialah mencari secara berulang perkataan terpanjang yang mungkin dalam teks. Walau bagaimanapun, ini boleh membawa kepada hasil yang tidak optimum.

Algoritma Berdasarkan Frekuensi

Sebaliknya, kita boleh mengeksploitasi kekerapan relatif perkataan dalam bahasa untuk meningkatkan ketepatan:

1. Modelkan Taburan Perkataan: Andaikan perkataan diedarkan secara bebas dan ikut undang-undang Zipf, di mana kebarangkalian perkataan adalah berkadar songsang dengan pangkatnya.
2. Tentukan Kos Perkataan: Kos sesuatu perkataan ditakrifkan sebagai logaritma songsang kebarangkaliannya.

3. Pendekatan Pengaturcaraan Dinamik:

   • Memulakan tatasusunan kos di mana yang pertama elemen ialah 0.
   • Bagi setiap aksara dalam teks, cari perkataan yang meminimumkan jumlah kos untuk aksara sehingga tahap itu.
   • Undur dari penghujung untuk membina semula urutan perkataan kos minimum .

Pelaksanaan Kod

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

wordcost = {}  # Dictionary of word costs using Zipf's law

maxword = max(len(word) for word in wordcost)

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((wordcost.get(s[i - k - 1:i], 9e999) + c, 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>

Hasil

Algoritma ini dapat membahagikan teks dengan tepat ke dalam senarai perkataan, walaupun dalam ketiadaan ruang.

Contoh:

Input: "tableapplechairtablecupboard..."
Output: ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], ...]

Pengoptimuman:

• Pokok Akhiran : Dengan membina pepohon akhiran daripada senarai perkataan, carian calon boleh dipercepatkan.
• Pemisahan Blok Teks: Untuk input teks yang besar, teks boleh dibahagikan kepada blok untuk meminimumkan penggunaan memori sambil mengekalkan ketepatan.

Atas ialah kandungan terperinci Bagaimanakah kita boleh memisahkan rentetan teks perkataan bercantum tanpa ruang kepada perkataan individu dengan cekap?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!