Bagaimana cara membagi teks tanpa spasi menjadi daftar kata?

Masukan: "tableapplechairtablecupboard..." banyak kata

Algoritma apa yang efisien untuk membagi teks seperti itu ke dalam daftar kata dan mendapatkan:

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

Hal pertama yang terlintas dalam pikiran adalah menelusuri semua kemungkinan kata (dimulai dengan huruf pertama) dan menemukan kata terpanjang mungkin, lanjutkan dari position=word_position+len(word)

NB
Kami memiliki daftar semua kemungkinan kata.
Kata "cupboard" bisa "cup" dan "board", pilih terpanjang.
Bahasa: python, tetapi yang utama adalah algoritmanya sendiri.

Algoritme yang naif tidak akan memberikan hasil yang baik jika diterapkan pada data dunia nyata. Berikut adalah algoritme 20 baris yang memanfaatkan frekuensi kata relatif untuk memberikan hasil yang akurat untuk teks kata nyata.

(Jika Anda menginginkan jawaban atas pertanyaan awal Anda yang tidak menggunakan frekuensi kata, Anda perlu memperjelas apa yang sebenarnya dimaksud dengan "kata terpanjang": apakah lebih baik memiliki kata 20 huruf dan sepuluh kata 3 huruf, atau lebih baik memiliki lima kata 10 huruf? Setelah Anda menentukan definisi yang tepat, Anda hanya perlu mengubah definisi baris wordcostuntuk mencerminkan arti yang dimaksudkan.)

Ide

Cara terbaik untuk melanjutkan adalah memodelkan distribusi keluaran. Perkiraan pertama yang baik adalah menganggap semua kata terdistribusi secara independen. Maka Anda hanya perlu mengetahui frekuensi relatif dari semua kata. Masuk akal untuk mengasumsikan bahwa mereka mengikuti hukum Zipf, yaitu kata dengan peringkat n dalam daftar kata memiliki probabilitas kira-kira 1 / ( n log N ) di mana N adalah jumlah kata dalam kamus.

Setelah Anda memperbaiki model, Anda dapat menggunakan pemrograman dinamis untuk menyimpulkan posisi spasi. Kalimat yang paling mungkin adalah kalimat yang memaksimalkan produk dari probabilitas setiap kata, dan mudah untuk menghitungnya dengan pemrograman dinamis. Alih-alih langsung menggunakan probabilitas, kami menggunakan biaya yang didefinisikan sebagai logaritma dari kebalikan dari probabilitas untuk menghindari luapan.

Kode

from math import log

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

def infer_spaces(s):
    """Uses dynamic programming to infer the location of spaces in a string
    without spaces."""

    # Find the best match for the i first characters, assuming cost has
    # been built for the i-1 first characters.
    # Returns a pair (match_cost, match_length).
    def best_match(i):
        candidates = enumerate(reversed(cost[max(0, i-maxword):i]))
        return min((c + wordcost.get(s[i-k-1:i], 9e999), k+1) for k,c in candidates)

    # Build the cost array.
    cost = [0]
    for i in range(1,len(s)+1):
        c,k = best_match(i)
        cost.append(c)

    # Backtrack to recover the minimal-cost string.
    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))

yang dapat Anda gunakan dengan

s = 'thumbgreenappleactiveassignmentweeklymetaphor'
print(infer_spaces(s))

Hasil

Saya menggunakan kamus 125k kata yang cepat dan kotor yang saya kumpulkan dari sebagian kecil Wikipedia.

Sebelum: jempol hijauaplikasi aktifmetafora mingguan.
Sesudah: jempol apel hijau aktif tugas metafora mingguan.

Sebelum: ada banyak informasi tambahan yang lembut dari komentar orang-orangyangdibagikanfromhtmltetapitermasuk karakter yang dibatasidalamamukaamplethumbhijauapartugas aktifminggu sekali metapho seringmenutupiapel hijaudengan lingkaran gondoksohavedibebankanuntuk mempertanyakan apakah kata-katadibuatdengan cara tercepat.

Setelah: ada banyak informasi teks dari komentar orang yang diurai dari html tetapi tidak ada karakter yang dipisahkan di dalamnya misalnya jempol apel aktif tugas metafora mingguan ternyata ada jempol apel hijau dll dalam string saya juga memiliki kamus besar untuk menanyakan apakah kata tersebut masuk akal jadi apa cara ekstraksi tercepat terima kasih.

Sebelum: gelap dan badai salju

Sesudah: itu adalah malam yang gelap dan badai, hujan turun dengan derasnya kecuali pada interval sesekali ketika diperiksa oleh hembusan angin kencang yang menyapu jalan karena di london itulah pemandangan kami berderak di sepanjang atap rumah dan dengan keras membuat gelisah sedikit nyala lampu yang berjuang melawan kegelapan.

Seperti yang Anda lihat, ini pada dasarnya tanpa cela. Bagian terpenting adalah memastikan daftar kata Anda dilatih untuk korpus yang mirip dengan apa yang sebenarnya akan Anda hadapi, jika tidak, hasilnya akan sangat buruk.

Optimasi

Implementasinya menghabiskan sejumlah waktu dan memori linier, sehingga cukup efisien. Jika Anda membutuhkan percepatan lebih lanjut, Anda dapat membuat pohon sufiks dari daftar kata untuk mengurangi ukuran kumpulan kandidat.

Jika Anda perlu memproses string berurutan yang sangat besar, sebaiknya pisahkan string tersebut untuk menghindari penggunaan memori yang berlebihan. Misalnya, Anda dapat memproses teks dalam blok 10.000 karakter ditambah margin 1000 karakter di kedua sisi untuk menghindari efek batas. Ini akan meminimalkan penggunaan memori dan hampir pasti tidak akan berpengaruh pada kualitas.

Berdasarkan karya luar biasa di jawaban atas , saya telah membuat pippaket agar mudah digunakan.

>>> import wordninja
>>> wordninja.split('derekanderson')
['derek', 'anderson']

Untuk menginstal, jalankan pip install wordninja.

Satu-satunya perbedaan kecil. Ini mengembalikan a listdaripada a str, berfungsi di python3, itu termasuk daftar kata dan membagi dengan benar bahkan jika ada karakter non-alfa (seperti garis bawah, tanda hubung, dll).

Terima kasih sekali lagi kepada Manusia Generik!

https://github.com/keredson/wordninja

Berikut solusi menggunakan pencarian rekursif:

def find_words(instring, prefix = '', words = None):
    if not instring:
        return []
    if words is None:
        words = set()
        with open('/usr/share/dict/words') as f:
            for line in f:
                words.add(line.strip())
    if (not prefix) and (instring in words):
        return [instring]
    prefix, suffix = prefix + instring[0], instring[1:]
    solutions = []
    # Case 1: prefix in solution
    if prefix in words:
        try:
            solutions.append([prefix] + find_words(suffix, '', words))
        except ValueError:
            pass
    # Case 2: prefix not in solution
    try:
        solutions.append(find_words(suffix, prefix, words))
    except ValueError:
        pass
    if solutions:
        return sorted(solutions,
                      key = lambda solution: [len(word) for word in solution],
                      reverse = True)[0]
    else:
        raise ValueError('no solution')

print(find_words('tableapplechairtablecupboard'))
print(find_words('tableprechaun', words = set(['tab', 'table', 'leprechaun'])))

hasil

['table', 'apple', 'chair', 'table', 'cupboard']
['tab', 'leprechaun']

Menggunakan struktur data trie , yang menyimpan daftar kemungkinan kata, tidaklah terlalu rumit untuk melakukan hal berikut:

1. Penunjuk muka (dalam string gabungan)
2. Cari dan simpan node yang sesuai di trie
3. Jika simpul trie memiliki anak (misalnya ada kata yang lebih panjang), lanjutkan ke 1.
4. Jika simpul tercapai tidak memiliki anak, kecocokan kata terpanjang terjadi; tambahkan kata (disimpan dalam node atau hanya bersambung selama trie traversal) ke daftar hasil, setel ulang penunjuk dalam tahap percobaan (atau setel ulang referensi), dan mulai lagi

Solusi Unutbu cukup dekat tetapi saya menemukan kodenya sulit untuk dibaca, dan itu tidak memberikan hasil yang diharapkan. Solusi Generic Human memiliki kekurangan yaitu membutuhkan frekuensi kata. Tidak sesuai untuk semua kasus penggunaan.

Berikut solusi sederhana menggunakan algoritma Divide and Conquer .

1. Ini mencoba untuk meminimalkan jumlah kata Eg find_words('cupboard')akan kembali ['cupboard']daripada ['cup', 'board'](dengan asumsi itu cupboard, cupdan boardberada dalam kamus)
2. Solusi optimal adalah tidak unik , pelaksanaan bawah kembali sebuah solusi. find_words('charactersin')bisa kembali ['characters', 'in']atau mungkin akan kembali ['character', 'sin'](seperti yang terlihat di bawah). Anda dapat dengan mudah memodifikasi algoritme untuk mengembalikan semua solusi optimal.
3. Dalam implementasi ini, solusi dibuat memo agar berjalan dalam waktu yang wajar.

Kode:

words = set()
with open('/usr/share/dict/words') as f:
    for line in f:
        words.add(line.strip())

solutions = {}
def find_words(instring):
    # First check if instring is in the dictionnary
    if instring in words:
        return [instring]
    # No... But maybe it's a result we already computed
    if instring in solutions:
        return solutions[instring]
    # Nope. Try to split the string at all position to recursively search for results
    best_solution = None
    for i in range(1, len(instring) - 1):
        part1 = find_words(instring[:i])
        part2 = find_words(instring[i:])
        # Both parts MUST have a solution
        if part1 is None or part2 is None:
            continue
        solution = part1 + part2
        # Is the solution found "better" than the previous one?
        if best_solution is None or len(solution) < len(best_solution):
            best_solution = solution
    # Remember (memoize) this solution to avoid having to recompute it
    solutions[instring] = best_solution
    return best_solution

Ini akan memakan waktu sekitar 5 detik pada mesin 3GHz saya:

result = find_words("thereismassesoftextinformationofpeoplescommentswhichisparsedfromhtmlbuttherearenodelimitedcharactersinthemforexamplethumbgreenappleactiveassignmentweeklymetaphorapparentlytherearethumbgreenappleetcinthestringialsohavealargedictionarytoquerywhetherthewordisreasonablesowhatsthefastestwayofextractionthxalot")
assert(result is not None)
print ' '.join(result)

Massa informasi teks komentar orang-orang yang diurai dari html tetapi tidak ada karakter yang dibatasi dosa mereka misalnya jempol apel aktif tugas metafora mingguan ternyata ada jempol apel hijau dll dalam string saya juga memiliki kamus besar untuk menanyakan apakah Kata itu masuk akal jadi apa cara ekstraksi tercepat terima kasih

Jawabannya oleh https://stackoverflow.com/users/1515832/generic-human sangat bagus. Tetapi implementasi terbaik dari ini yang pernah saya lihat ditulis sendiri oleh Peter Norvig dalam bukunya 'Beautiful Data'.

Sebelum saya menempelkan kodenya, izinkan saya menjelaskan mengapa metode Norvig lebih akurat (meskipun sedikit lebih lambat dan lebih lama dalam hal kode).

1) Datanya sedikit lebih baik - baik dalam hal ukuran dan presisi (ia menggunakan jumlah kata daripada peringkat sederhana) 2) Lebih penting lagi, logika di balik n-gram yang benar-benar membuat pendekatannya begitu akurat .

Contoh yang dia berikan dalam bukunya adalah masalah pemisahan string 'sitdown'. Sekarang metode pemisahan string non-bigram akan mempertimbangkan p ('sit') * p ('down'), dan jika ini kurang dari p ('sitdown') - yang akan sering terjadi - TIDAK akan terpecah itu, tapi kami menginginkannya (sebagian besar waktu).

Namun ketika Anda memiliki model bigram, Anda dapat menilai p ('sit down') sebagai bigram vs p ('sitdown') dan yang pertama menang. Pada dasarnya, jika Anda tidak menggunakan bigram, ini memperlakukan probabilitas kata-kata yang Anda pisahkan sebagai independen, yang tidak terjadi, beberapa kata lebih mungkin muncul satu demi satu. Sayangnya itu juga kata-kata yang sering menempel bersama dalam banyak kasus dan membingungkan splitter.

Berikut link ke datanya (data untuk 3 masalah terpisah dan segmentasi hanya satu. Silakan baca bab untuk detailnya): http://norvig.com/ngrams/

dan ini tautan ke kode: http://norvig.com/ngrams/ngrams.py

Tautan ini sudah aktif beberapa saat, tetapi saya akan menyalin dan menempelkan bagian segmentasi kode di sini

import re, string, random, glob, operator, heapq
from collections import defaultdict
from math import log10

def memo(f):
    "Memoize function f."
    table = {}
    def fmemo(*args):
        if args not in table:
            table[args] = f(*args)
        return table[args]
    fmemo.memo = table
    return fmemo

def test(verbose=None):
    """Run some tests, taken from the chapter.
    Since the hillclimbing algorithm is randomized, some tests may fail."""
    import doctest
    print 'Running tests...'
    doctest.testfile('ngrams-test.txt', verbose=verbose)

################ Word Segmentation (p. 223)

@memo
def segment(text):
    "Return a list of words that is the best segmentation of text."
    if not text: return []
    candidates = ([first]+segment(rem) for first,rem in splits(text))
    return max(candidates, key=Pwords)

def splits(text, L=20):
    "Return a list of all possible (first, rem) pairs, len(first)<=L."
    return [(text[:i+1], text[i+1:]) 
            for i in range(min(len(text), L))]

def Pwords(words): 
    "The Naive Bayes probability of a sequence of words."
    return product(Pw(w) for w in words)

#### Support functions (p. 224)

def product(nums):
    "Return the product of a sequence of numbers."
    return reduce(operator.mul, nums, 1)

class Pdist(dict):
    "A probability distribution estimated from counts in datafile."
    def __init__(self, data=[], N=None, missingfn=None):
        for key,count in data:
            self[key] = self.get(key, 0) + int(count)
        self.N = float(N or sum(self.itervalues()))
        self.missingfn = missingfn or (lambda k, N: 1./N)
    def __call__(self, key): 
        if key in self: return self[key]/self.N  
        else: return self.missingfn(key, self.N)

def datafile(name, sep='\t'):
    "Read key,value pairs from file."
    for line in file(name):
        yield line.split(sep)

def avoid_long_words(key, N):
    "Estimate the probability of an unknown word."
    return 10./(N * 10**len(key))

N = 1024908267229 ## Number of tokens

Pw  = Pdist(datafile('count_1w.txt'), N, avoid_long_words)

#### segment2: second version, with bigram counts, (p. 226-227)

def cPw(word, prev):
    "Conditional probability of word, given previous word."
    try:
        return P2w[prev + ' ' + word]/float(Pw[prev])
    except KeyError:
        return Pw(word)

P2w = Pdist(datafile('count_2w.txt'), N)

@memo 
def segment2(text, prev='<S>'): 
    "Return (log P(words), words), where words is the best segmentation." 
    if not text: return 0.0, [] 
    candidates = [combine(log10(cPw(first, prev)), first, segment2(rem, first)) 
                  for first,rem in splits(text)] 
    return max(candidates) 

def combine(Pfirst, first, (Prem, rem)): 
    "Combine first and rem results into one (probability, words) pair." 
    return Pfirst+Prem, [first]+rem 

Berikut adalah jawaban yang diterima yang diterjemahkan ke JavaScript (membutuhkan node.js, dan file "wordninja_words.txt" dari https://github.com/keredson/wordninja ):

var fs = require("fs");

var splitRegex = new RegExp("[^a-zA-Z0-9']+", "g");
var maxWordLen = 0;
var wordCost = {};

fs.readFile("./wordninja_words.txt", 'utf8', function(err, data) {
    if (err) {
        throw err;
    }
    var words = data.split('\n');
    words.forEach(function(word, index) {
        wordCost[word] = Math.log((index + 1) * Math.log(words.length));
    })
    words.forEach(function(word) {
        if (word.length > maxWordLen)
            maxWordLen = word.length;
    });
    console.log(maxWordLen)
    splitRegex = new RegExp("[^a-zA-Z0-9']+", "g");
    console.log(split(process.argv[2]));
});


function split(s) {
    var list = [];
    s.split(splitRegex).forEach(function(sub) {
        _split(sub).forEach(function(word) {
            list.push(word);
        })
    })
    return list;
}
module.exports = split;


function _split(s) {
    var cost = [0];

    function best_match(i) {
        var candidates = cost.slice(Math.max(0, i - maxWordLen), i).reverse();
        var minPair = [Number.MAX_SAFE_INTEGER, 0];
        candidates.forEach(function(c, k) {
            if (wordCost[s.substring(i - k - 1, i).toLowerCase()]) {
                var ccost = c + wordCost[s.substring(i - k - 1, i).toLowerCase()];
            } else {
                var ccost = Number.MAX_SAFE_INTEGER;
            }
            if (ccost < minPair[0]) {
                minPair = [ccost, k + 1];
            }
        })
        return minPair;
    }

    for (var i = 1; i < s.length + 1; i++) {
        cost.push(best_match(i)[0]);
    }

    var out = [];
    i = s.length;
    while (i > 0) {
        var c = best_match(i)[0];
        var k = best_match(i)[1];
        if (c == cost[i])
            console.log("Alert: " + c);

        var newToken = true;
        if (s.slice(i - k, i) != "'") {
            if (out.length > 0) {
                if (out[-1] == "'s" || (Number.isInteger(s[i - 1]) && Number.isInteger(out[-1][0]))) {
                    out[-1] = s.slice(i - k, i) + out[-1];
                    newToken = false;
                }
            }
        }

        if (newToken) {
            out.push(s.slice(i - k, i))
        }

        i -= k

    }
    return out.reverse();
}

Jika Anda mengkompilasi daftar kata menjadi DFA (yang akan sangat lambat), maka waktu yang dibutuhkan untuk mencocokkan masukan akan sebanding dengan panjang string (sebenarnya, hanya sedikit lebih lambat daripada hanya mengulang string).

Ini secara efektif adalah versi yang lebih umum dari algoritma trie yang telah disebutkan sebelumnya. Saya hanya menyebutkannya jika tidak lengkap - hingga saat ini, belum ada implementasi DFA yang bisa Anda gunakan. RE2 akan berfungsi, tetapi saya tidak tahu apakah pengikatan Python memungkinkan Anda menyesuaikan seberapa besar Anda mengizinkan DFA sebelum hanya membuang data DFA yang dikompilasi dan melakukan pencarian NFA.

Sepertinya kemunduran yang cukup biasa akan dilakukan. Mulailah dari awal string. Pindai sampai Anda mendapatkan sepatah kata pun. Kemudian, panggil fungsi tersebut di string lainnya. Fungsi mengembalikan "salah" jika memindai sepenuhnya ke kanan tanpa mengenali satu kata pun. Jika tidak, kembalikan kata yang ditemukan dan daftar kata yang dikembalikan oleh panggilan rekursif.

Contoh: "tableapple". Menemukan "tab", lalu "leap", tetapi tidak ada kata dalam "ple". Tidak ada kata lain dalam "leapple". Menemukan "tabel", lalu "aplikasi". "le" bukan sebuah kata, jadi apel mencoba, mengenali, kembali.

Untuk mendapatkan waktu yang lebih lama, lanjutkan, hanya mengeluarkan (daripada mengembalikan) solusi yang benar; kemudian, pilih yang optimal dengan kriteria apa pun yang Anda pilih (maxmax, minmax, average, dll.)

Berdasarkan solusi unutbu, saya telah menerapkan versi Java:

private static List<String> splitWordWithoutSpaces(String instring, String suffix) {
    if(isAWord(instring)) {
        if(suffix.length() > 0) {
            List<String> rest = splitWordWithoutSpaces(suffix, "");
            if(rest.size() > 0) {
                List<String> solutions = new LinkedList<>();
                solutions.add(instring);
                solutions.addAll(rest);
                return solutions;
            }
        } else {
            List<String> solutions = new LinkedList<>();
            solutions.add(instring);
            return solutions;
        }

    }
    if(instring.length() > 1) {
        String newString = instring.substring(0, instring.length()-1);
        suffix = instring.charAt(instring.length()-1) + suffix;
        List<String> rest = splitWordWithoutSpaces(newString, suffix);
        return rest;
    }
    return Collections.EMPTY_LIST;
}

Memasukkan: "tableapplechairtablecupboard"

Keluaran: [table, apple, chair, table, cupboard]

Memasukkan: "tableprechaun"

Keluaran: [tab, leprechaun]

Untuk bahasa Jerman ada CharSplit yang menggunakan pembelajaran mesin dan berfungsi cukup baik untuk string beberapa kata.

https://github.com/dtuggener/CharSplit

Memperluas saran @ miku untuk menggunakan a Trie, append-only Trierelatif mudah diterapkan di python:

class Node:
    def __init__(self, is_word=False):
        self.children = {}
        self.is_word = is_word

class TrieDictionary:
    def __init__(self, words=tuple()):
        self.root = Node()
        for word in words:
            self.add(word)

    def add(self, word):
        node = self.root
        for c in word:
            node = node.children.setdefault(c, Node())
        node.is_word = True

    def lookup(self, word, from_node=None):
        node = self.root if from_node is None else from_node
        for c in word:
            try:
                node = node.children[c]
            except KeyError:
                return None

        return node

Kami kemudian dapat membangun Triekamus berbasis dari sekumpulan kata:

dictionary = {"a", "pea", "nut", "peanut", "but", "butt", "butte", "butter"}
trie_dictionary = TrieDictionary(words=dictionary)

Yang akan menghasilkan pohon yang terlihat seperti ini ( *menunjukkan awal atau akhir kata):

* -> a*
 \\\ 
  \\\-> p -> e -> a*
   \\              \-> n -> u -> t*
    \\
     \\-> b -> u -> t*
      \\             \-> t*
       \\                 \-> e*
        \\                     \-> r*
         \
          \-> n -> u -> t*

Kita dapat memasukkan ini ke dalam solusi dengan menggabungkannya dengan heuristik tentang cara memilih kata. Misalnya kita dapat memilih kata yang lebih panjang daripada kata yang lebih pendek:

def using_trie_longest_word_heuristic(s):
    node = None
    possible_indexes = []

    # O(1) short-circuit if whole string is a word, doesn't go against longest-word wins
    if s in dictionary:
        return [ s ]

    for i in range(len(s)):
        # traverse the trie, char-wise to determine intermediate words
        node = trie_dictionary.lookup(s[i], from_node=node)

        # no more words start this way
        if node is None:
            # iterate words we have encountered from biggest to smallest
            for possible in possible_indexes[::-1]:
                # recurse to attempt to solve the remaining sub-string
                end_of_phrase = using_trie_longest_word_heuristic(s[possible+1:])

                # if we have a solution, return this word + our solution
                if end_of_phrase:
                    return [ s[:possible+1] ] + end_of_phrase

            # unsolvable
            break

        # if this is a leaf, append the index to the possible words list
        elif node.is_word:
            possible_indexes.append(i)

    # empty string OR unsolvable case 
    return []

Kita bisa menggunakan fungsi ini seperti ini:

>>> using_trie_longest_word_heuristic("peanutbutter")
[ "peanut", "butter" ]

Karena kami mempertahankan posisi kami di Triesaat kami mencari lagi dan kata-kata lagi, kami melintasi triepaling banyak sekali per solusi yang mungkin (bukan 2kali untuk peanut: pea, peanut). Hubungan pendek terakhir menyelamatkan kita dari berjalan dengan bijak melalui tali dalam kasus terburuk.

Hasil akhirnya hanya sedikit dari inspeksi:

'peanutbutter' - not a word, go charwise
'p' - in trie, use this node
'e' - in trie, use this node
'a' - in trie and edge, store potential word and use this node
'n' - in trie, use this node
'u' - in trie, use this node
't' - in trie and edge, store potential word and use this node
'b' - not in trie from `peanut` vector
'butter' - remainder of longest is a word

Manfaat dari solusi ini adalah kenyataan bahwa Anda mengetahui dengan sangat cepat jika ada kata yang lebih panjang dengan awalan tertentu, yang menghemat kebutuhan untuk menguji kombinasi urutan secara menyeluruh terhadap kamus. Itu juga membuat untuk sebuahunsolvable jawaban relatif murah untuk implementasi lain.

Kelemahan dari solusi ini adalah jejak memori yang besar untuk biaya triedan biaya pembuatan di triemuka.

Jika Anda memiliki daftar lengkap kata-kata yang terkandung dalam string:

word_list = ["table", "apple", "chair", "cupboard"]

Menggunakan pemahaman daftar untuk mengulang daftar untuk menemukan kata dan berapa kali kata itu muncul.

string = "tableapplechairtablecupboard"

def split_string(string, word_list):

    return ("".join([(item + " ")*string.count(item.lower()) for item in word_list if item.lower() in string])).strip()

Fungsi mengembalikan stringoutput kata-kata dalam urutan daftartable table apple chair cupboard

Terima kasih banyak atas bantuannya di https://github.com/keredson/wordninja/

Kontribusi kecil yang sama di Jawa dari sisi saya.

Metode publik splitContiguousWordsdapat disematkan dengan 2 metode lain di kelas yang memiliki ninja_words.txt di direktori yang sama (atau dimodifikasi sesuai pilihan pembuat kode). Dan metode splitContiguousWordstersebut dapat digunakan untuk tujuan tersebut.

public List<String> splitContiguousWords(String sentence) {

    String splitRegex = "[^a-zA-Z0-9']+";
    Map<String, Number> wordCost = new HashMap<>();
    List<String> dictionaryWords = IOUtils.linesFromFile("ninja_words.txt", StandardCharsets.UTF_8.name());
    double naturalLogDictionaryWordsCount = Math.log(dictionaryWords.size());
    long wordIdx = 0;
    for (String word : dictionaryWords) {
        wordCost.put(word, Math.log(++wordIdx * naturalLogDictionaryWordsCount));
    }
    int maxWordLength = Collections.max(dictionaryWords, Comparator.comparing(String::length)).length();
    List<String> splitWords = new ArrayList<>();
    for (String partSentence : sentence.split(splitRegex)) {
        splitWords.add(split(partSentence, wordCost, maxWordLength));
    }
    log.info("Split word for the sentence: {}", splitWords);
    return splitWords;
}

private String split(String partSentence, Map<String, Number> wordCost, int maxWordLength) {
    List<Pair<Number, Number>> cost = new ArrayList<>();
    cost.add(new Pair<>(Integer.valueOf(0), Integer.valueOf(0)));
    for (int index = 1; index < partSentence.length() + 1; index++) {
        cost.add(bestMatch(partSentence, cost, index, wordCost, maxWordLength));
    }
    int idx = partSentence.length();
    List<String> output = new ArrayList<>();
    while (idx > 0) {
        Pair<Number, Number> candidate = bestMatch(partSentence, cost, idx, wordCost, maxWordLength);
        Number candidateCost = candidate.getKey();
        Number candidateIndexValue = candidate.getValue();
        if (candidateCost.doubleValue() != cost.get(idx).getKey().doubleValue()) {
            throw new RuntimeException("Candidate cost unmatched; This should not be the case!");
        }
        boolean newToken = true;
        String token = partSentence.substring(idx - candidateIndexValue.intValue(), idx);
        if (token != "\'" && output.size() > 0) {
            String lastWord = output.get(output.size() - 1);
            if (lastWord.equalsIgnoreCase("\'s") ||
                    (Character.isDigit(partSentence.charAt(idx - 1)) && Character.isDigit(lastWord.charAt(0)))) {
                output.set(output.size() - 1, token + lastWord);
                newToken = false;
            }
        }
        if (newToken) {
            output.add(token);
        }
        idx -= candidateIndexValue.intValue();
    }
    return String.join(" ", Lists.reverse(output));
}


private Pair<Number, Number> bestMatch(String partSentence, List<Pair<Number, Number>> cost, int index,
                      Map<String, Number> wordCost, int maxWordLength) {
    List<Pair<Number, Number>> candidates = Lists.reverse(cost.subList(Math.max(0, index - maxWordLength), index));
    int enumerateIdx = 0;
    Pair<Number, Number> minPair = new Pair<>(Integer.MAX_VALUE, Integer.valueOf(enumerateIdx));
    for (Pair<Number, Number> pair : candidates) {
        ++enumerateIdx;
        String subsequence = partSentence.substring(index - enumerateIdx, index).toLowerCase();
        Number minCost = Integer.MAX_VALUE;
        if (wordCost.containsKey(subsequence)) {
            minCost = pair.getKey().doubleValue() + wordCost.get(subsequence).doubleValue();
        }
        if (minCost.doubleValue() < minPair.getKey().doubleValue()) {
            minPair = new Pair<>(minCost.doubleValue(), enumerateIdx);
        }
    }
    return minPair;
}

Ini akan membantu

from wordsegment import load, segment
load()
segment('providesfortheresponsibilitiesofperson')

Anda perlu mengidentifikasi kosakata Anda - mungkin daftar kata gratis apa pun bisa digunakan.

Setelah selesai, gunakan kosakata itu untuk membangun pohon sufiks, dan cocokkan aliran masukan Anda dengan itu: http://en.wikipedia.org/wiki/Suffix_tree