Hai bisogno di organizzare le parole in base ai loro componenti, in qualsiasi altro modo oltre alla forza bruta?

Question

Hai bisogno di organizzare le parole in base ai loro componenti, in qualsiasi altro modo oltre alla forza bruta?

#1 da (1 voti)
#2 da (0 voti)

1

Non sono sicuro che questo processo abbia un nome.

Ho alcune parole (circa 9000). Sono in giapponese, ma cercherò di spiegarlo usando parole inglesi. Voglio classificare le parole in base ai componenti (in inglese, lettere).

A

B

C

play act bar

Questo dovrebbe creare:

A: riproduci

B: bar

C: act

Ora, 'a' appare in tutte e 3 le parole, ma voglio assicurarmi che ogni categoria (lettera) abbia almeno una parola. Ora, avrebbe senso cancellare una parola dopo che è stata usata, ma ci sono alcuni casi in cui 2 lettere costituiscono una parola e questa è l'unica parola di ogni lettera - quindi mi piacerebbe renderlo conto in qualche modo.

Esiste un approccio per risolvere questo oltre alla forza bruta? Programmazione dinamica forse? Anche un nome per questo processo (se esiste) sarebbe fantastico.

java algorithms dynamic-programming

posta Lathan 21.08.2014 - 19:39

fonte

2 risposte

Leggi altre domande sui tag java algorithms dynamic-programming

Utilizzo di Mockito.reset FFmpeg: Posso sostituire libx264 con OpenH264 per andare su LGPL?

score 1 · Answer 1

Lucene è una potente libreria usata per fare una varietà di ricerche e discorsi di testo e potrebbe valere la pena dare un'occhiata a . Il tipico caso d'uso è la ricerca full-text, ma è piuttosto basato sui componenti, quindi potresti certamente creare un analizzatore o uno stemmer personalizzato per arrivare dove vuoi essere.

score 0 · Answer 2

Puoi esprimere questo come un problema di flusso massimo. Un problema di flusso massimo ottimizza un flusso in una rete. Può essere usato per risolvere problemi di assegnazione. Vuoi assegnare parole alle categorie.

Devi compilare un grafico come segue:

Ogni categoria e ogni parola è un nodo, a cui devi aggiungere un nodo iniziale e un nodo finale.

Dal nodo di inizio, aggiungi un margine andando a ciascuna categoria. Da ogni categoria aggiungi un vantaggio per ogni parola compatibile con la categoria. Da ogni parola, aggiungi un bordo andando al nodo finale. Tutti i bordi hanno capacità 1.

In questo grafico si desidera massimizzare il flusso che va dal nodo iniziale al nodo finale. Il Ford-Fulkerson è particolarmente interessante perché funziona con pesi interi e restituisce una soluzione in interi.

La soluzione assegna una parola a ciascuna categoria seguendo semplicemente per ogni categoria il bordo ha un flusso positivo. Se è impossibile assegnare una parola a tutte le categorie, restituirà l'assegnazione che massimizza il numero di categorie corrispondenti a una parola.

Se hai più parole di categorie o parole lasciate, puoi assegnare le parole rimanenti alla prima categoria corrispondente.

Ciò garantirà che a un massimo di categorie corrisponde almeno una parola corrispondente.