Geek Answers Handbook

Algorithms find the most common string sequence of length 3

"Given multiple arrays of names, find the most common sequence of names of length 3 (sequence of length 3), if it exists"

For example: Given 3 arrays of names:

Ana John Maria Paul Sharon Ana John Maria Tiffany Ted

The output will be Ana John Maria , as this sequence occurs twice, in the first and third arrays.

I can not find the right solution for this.

Can someone point me in the right direction? Maybe this is a well-known algorithm for this. Can someone give me a link? Thanks

+4
source share
2 answers

Combine arrays into a tree like trie, where each node is not a single letter, but a whole name. This should make it easier for you to find and count subsequences. In fact, I strongly suspect that there is a standard algorithm for this task that you can find.

Update: see the algorithms using suffixes: http://en.wikipedia.org/wiki/Suffix_tree

+4
source

A simple approach would be to take sequences of 3 and put them in a HashTable . As soon as you come across sequence 3, you increase the corresponding counter of counter events. In the end, just return the most frequent appearance / sequence. This can be found by scanning the HashTable to record with the maximum occurrence value. An example in Java:

 public class Sequence { public List<String> sequenceOfThree(List<List<String>> names){ Map<List<String>, Integer> map = new HashMap<List<String>, Integer>(); for(List<String> nameList:names){ int startIdx = 0; int endIdx = 3; while(endIdx <= nameList.size()){ List<String> subsequence = nameList.subList(startIdx, endIdx); //add to map Integer count = map.get(subsequence); if(count == null){ count = 0; } map.put(subsequence, count + 1); startIdx++; endIdx++; } } Integer max = Integer.MIN_VALUE; List<String> result = Collections.emptyList(); for(Entry<List<String>, Integer> entries:map.entrySet()){ if(entries.getValue() > max){ max = entries.getValue(); result = entries.getKey(); } } return result; } /** * @param args */ public static void main(String[] args) { List<List<String>> names = new ArrayList<List<String>>(); names.add(Arrays.asList(new String[]{"Ana", "John", "Maria"})); names.add(Arrays.asList(new String[]{"Paul"})); names.add(Arrays.asList(new String[] "Sharon", "Ana", "John", "Maria", "Tiffany" ,"Ted"})); System.out.println(new Sequence().sequenceOfThree(names)); } }
+2
source

More articles:


All Articles