2
$\begingroup$

Given a word list of $N$ words formed from a language of $M$ characters, where each word is composed of $n \geq 1$ not necessarily distinct characters, how can I find the best set of $k<M$ characters to learn, where "best" is defined as the set of $k$ with which the most complete words can be spelled. Ie, if I know these $k$ characters I can spell $N_k$ words. What is the maximum $N_k$ for every $k$ and which characters should I choose?

Checking a given set of $k$ words is equivalent to a Scrabble problem, but searching the space becomes very hard very fast. This problem is of limited interest in English where $M=26$ but is more important in Chinese or Japanese where $M \sim 10^3$.

I thought of considering the bipartite graph of characters and the words that they make but I'm not sure what the best search strategy is. I'm somewhat pessimistic that this problem is strictly solvable and therefore I am willing to try heuristic or stochastic methods.

$\endgroup$
  • 3
    $\begingroup$ General comments: it's NP-hard (when all words have length two, it's the maximum subgraph problem), and for actual real-world languages, the heuristic "learn the k most common letters" will probably do you right. $\endgroup$ – Lopsy Apr 26 '15 at 17:56
  • $\begingroup$ NP-hard is useful, thanks. Of course most common would be the first approximation. However, I believe that better results can be obtained from more subtle network measurements. In any event, if there is no "real" solution, it frees me to experiment with less conventional methods. If I succeed, I'll post an answer. $\endgroup$ – mmdanziger Apr 26 '15 at 18:03
  • $\begingroup$ @Pal GD When all words have length two, the problem literally becomes an instance of the maximum subgraph problem. The maximum subgraph problem is: given a graph and an integer k, find the subgraph of size k with the most edges. $\endgroup$ – Lopsy Apr 27 '15 at 9:29
  • $\begingroup$ @Lopsy Ah, yes, I see. Very good :) It indeed is easily shown to be NP-complete and W[2]-hard by a reduction from Red-Blue Dominating set in bipartite graphs. Let the symbols be side A and the words side B. Now you need to find a subset of vertices in A that dominates all of B. $\endgroup$ – Pål GD Apr 27 '15 at 9:35
1
$\begingroup$

As Lopsy states, your problem is NP-hard, so you shouldn't expect an efficient algorithm for your problem.

Your problem is an instance of the maximum coverage problem (which is also NP-hard). This may help you find algorithms that will be helpful in your setting.

There are standard algorithms for the maximum coverage algorithm. There's a natural greedy algorithm; it achieves an approximation ratio of approximately 0.63.

Perhaps a better approach is to formulate this as an instance of integer linear programming (ILP), and then throw an off-the-shelf ILP solver at it (e.g., lp_solve, CPLEX). See Wikipedia for a description of how to do that. For your English example (alphabet size 26) it's possible this might give you an optimal solution, but for the Chinese language problem, you shouldn't expect this to terminate and give you the optimal solution within your lifetime. Instead, I suggest you let it run for a bounded time and do the best it can within that time bound. Standard ILP solvers will let you provide a time bound: e.g., run for 5 minutes and then give me the best solution you've found so for.

You will probably want to apply the following simple optimization. Replace each word with the set of letters it contains (so order doesn't matter and repetitions are ignored). Then, de-dup these sets, and include a weight for each set that counts how many times it appears. Thus, GRIN and RING map to the same set, {G,I,N,R}. This will reduce the problem size and might make the ILP solver run faster.

Depending upon your application, you might also want to weight the words by their frequency of occurrence in natural language and then solve the weighted maximum coverage problem, so that you place an extra emphasis on covering common words and a lower priority on covering rare words.

You can also search the literature for other algorithms for the maximum coverage problem, but I suspect the pragmatic answer is going to be to use ILP with a reasonable time bound.

$\endgroup$
1
$\begingroup$

If you take each word as a set of characters, you're looking for sets of size k that contain the most words as subsets. For a given word of j unique characters out of an alphabet of size N, you have (N-j) choose (k-j) possible supersets, ie all the sets of size k that have the original j characters plus any (k-j) others.

Some time ago I worked on an algorithm for a similar problem that might be modified for this case. I'll try to sketch how it would work in this case.

Briefly, the solution is to walk all the "words" through their candidate supersets (a factorial number) in a fixed order, identify any runs of identical values that indicate a number of words that fit in the same superset, and to save the run that's longest.

This is essentially an n-way merge, looking for runs of identical values on the output. I did this with a heap of iterators where I would pull the smallest value, count it, increment it (find the next superset in its range of possible supersets), and re-insert it into the heap. This process provably visits every possible superset and counts the words that it covers.

What makes this possibly tractable is a pruning rule that skips candidates with sub-maximal runs. What I realized while coding the above is that if my only interest is runs of length L or greater, then if I look L elements ahead I can see if the current run stops before L elements, and furthermore (with some careful reasoning) eliminate all intervening values from consideration and skip to whatever value is L elements ahead.

The problem I was solving originally was association-rule mining, which walks each set through its subsets rather than supersets, and this method worked well in that case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.