Text completion
- Task
Write a program that takes in a user inputted word and prints out possible words that are valid in the English dictionary. Please state any dictionaries or files/binaries/dependencies used in your program. Do show the similarity of the inputted word and outcome as a percentage. Any algorithm can be used to accomplish this task.
- Resources
Github Repo
Raw Text, Save as .txt file
Hamming Distance
Jaro-Winkler Distance
SoundEx Algorithm
SoundEx Algorithm Wiki
Dice's Coefficient
Dice Coefficient Wiki
- Possible Output
Input word: complition compaction : 80.00% similar. completion : 90.00% similar. completions : 81.82% similar. complexion : 80.00% similar.
- Extension
- How can you make the accuracy of your program higher?
Java
Github Repo Uses dependencies given. <lang Java> import java.io.File; import java.io.IOException; import java.net.URISyntaxException; import java.util.ArrayList; import java.util.Scanner;
//uses https://github.com/dwyl/english-words
public class textCompletionConcept {
public static int correct = 0; public static ArrayList<String> listed = new ArrayList<>(); public static void main(String[]args) throws IOException, URISyntaxException { Scanner input = new Scanner(System.in); System.out.println("Input word: "); String errorRode = input.next(); File file = new File(new File(textCompletionConcept.class.getProtectionDomain().getCodeSource().getLocation().toURI()).getPath() + File.separator + "words.txt"); Scanner reader = new Scanner(file); while(reader.hasNext()){ double percent; String compareToThis = reader.nextLine(); char[] s1 = errorRode.toCharArray(); char[] s2 = compareToThis.toCharArray(); int maxlen = Math.min(s1.length, s2.length); for (int index = 0; index < maxlen; index++) { String x = String.valueOf(s1[index]); String y = String.valueOf(s2[index]); if (x.equals(y)) { correct++; } } double length = Math.max(s1.length, s2.length); percent = correct / length; percent *= 100; boolean perfect = false; if (percent >= 80 && compareToThis.charAt(0) == errorRode.charAt(0)) { if(String.valueOf(percent).equals("100.00")){ perfect = true; } String addtoit = compareToThis + " : " + String.format("%.2f", percent) + "% similar."; listed.add(addtoit); } if(compareToThis.contains(errorRode) && !perfect && errorRode.length() * 2 > compareToThis.length()){ String addtoit = compareToThis + " : 80.00% similar."; listed.add(addtoit); } correct = 0; }
for(String x : listed){ if(x.contains("100.00% similar.")){ System.out.println(x); listed.clear(); break; } }
for(String x : listed){ System.out.println(x); } }
} </lang>
- Output
Input word: complition compaction : 80.00% similar. completion : 90.00% similar. completions : 81.82% similar. complexion : 80.00% similar. Process finished with exit code 0
Julia
See https://en.wikipedia.org/wiki/Levenshtein_distance, the number of one character edits to obtain one word from another. <lang julia>using StringDistances
const fname = download("https://www.mit.edu/~ecprice/wordlist.10000", "wordlist10000.txt") const words = read(fname, String) |> split .|> strip .|> string const wrd = "complition"
levdistof(n, string) = filter(w -> Levenshtein()(string, w) == n, words)
for n in 1:4
println("Words at Levenshtein distance of $n (", 100 - Int(round(100 * n / length(wrd))), "% similarity) from \"$wrd\": \n", levdistof(n, wrd), "\n")
end
</lang>
- Output:
Words at Levenshtein distance of 1 (90% similarity) from "complition": ["completion"] Words at Levenshtein distance of 2 (80% similarity) from "complition": ["coalition", "competition", "compilation", "composition"] Words at Levenshtein distance of 3 (70% similarity) from "complition": ["companion", "competitions", "completing", "complications", "computation", "condition"] Words at Levenshtein distance of 4 (60% similarity) from "complition": ["collection", "combination", "commission", "comparison", "compensation", "competing", "competitive", "complaint", "complete", "completed", "completely", "complexity", "compliance", "compliant", "compression", "computing", "conclusion", "conditions", "connection", "convention", "conviction", "cooperation", "corporation", "correction", "correlation", "corruption", "nomination", "opinion", "opposition", "option", "pollution", "population", "position", "simulation", "solution"]
Phix
uses levenshtein() from Levenshtein_distance#Phix <lang Phix>string word = "complition" sequence words = get_text(join_path({"demo","unixdict.txt"}),GT_LF_STRIPPED) function lt(string w, integer n) --function lt(string w, sequence nw) -- alt... -- {integer n, string word} = nw -- ...""
return levenshtein(w,word)=n
end function for n=1 to 4 do
printf(1,"Words at Levenshtein distance of %d (%g%% similarity) from \"%s\": \n%s\n", {n,100-round(100*n/length(word)),word,join_by(filter(words,lt,n),1,6)})
-- ..."" {n,100-round(100*n/length(word)),word,join_by(filter(words,lt,{n,word}),1,6)}) end for</lang>
- Output:
Words at Levenshtein distance of 1 (90% similarity) from "complition": completion Words at Levenshtein distance of 2 (80% similarity) from "complition": coalition competition compilation complexion composition Words at Levenshtein distance of 3 (70% similarity) from "complition": cognition collision combustion commotion companion compassion complain complicity compton compulsion compunction computation condition contrition demolition incompletion volition Words at Levenshtein distance of 4 (60% similarity) from "complition": abolition admonition ambition ammunition campion caption collusion combination commission communion compactify comparison compatriot competitive competitor complaint complete compliant complicate compliment compline compositor compression conception concision conclusion concretion congestion consolation contention convention convolution corruption cotillion decomposition depletion dominion gumption implosion imposition munition oblivion opinion opposition option pollution position simpleton soliton solution sorption templeton temptation tomlinson
Raku
(formerly Perl 6)
<lang perl6>sub MAIN ( Str $user_word = 'complition', Str $filename = 'words.txt' ) {
my @s1 = $user_word.comb; my @listed = gather for $filename.IO.lines -> $line { my @s2 = $line.comb;
my $correct = 100 * sum( @s1 Zeq @s2) / max(+@s1, +@s2);
my $score = ( $correct >= 100 and @s1[0] eq @s2[0] ) ?? 100 !! ( $correct >= 80 and @s1[0] eq @s2[0] ) ?? $correct !! ( $line.contains($user_word) and @s1 * 2 > @s2 ) ?? 80 !! 0; take [$score, $line] if $score; }
@listed = @listed[$_] with @listed.first: :k, { .[0] == 100 };
say "{.[0].fmt('%.2f')}% {.[1]}" for @listed;
}</lang>
- Output:
80.00% compaction 90.00% completion 81.82% completions 80.00% complexion
REXX
<lang rexx>/*REXX pgm finds (dictionary) words which can be found in a specified word wheel (grid).*/ parse arg what iFID . /*obtain optional arguments from the CL*/ if what==|what=="," then what= 'complition' /*Not specified? Then use the default.*/ if iFID==|iFID=="," then iFID= 'UNIXDICT.TXT' /* " " " " " " */ @abc= 'abcdefghijklmnopqrstuvwxyz' /*(Latin) lowercase letters to be used.*/ L= length(@abc) /* " " " the Latin letters. */ wrds= 0 /*# words that are in the dictionary. */ dups= 0 /*" " " " duplicates. */ ills= 0 /*" " " contain "not" letters.*/ say ' Reading the file: ' iFID /*align the text. */ @.= . /*non─duplicated dictionary words. */ $= /*the list of dictionary words in grid.*/
do recs=0 while lines(iFID)\==0 /*process all words in the dictionary. */ x= space( linein(iFID), 0) /*elide any blanks in the dictinary. */ if @.x\==. then do; dups= dups+1; iterate; end /*is this a duplicate? */ if \datatype(x,'M') then do; ills= ills+1; iterate; end /*has word non─letters? */ @.x= /*signify that X is a dictionary word*/ wrds= wrds + 1 /*bump the number of "good" dist. words*/ end /*recs*/
a= say ' number of records (words) in the dictionary: ' right( commas(recs), 9) say ' number of ill─formed words in the dictionary: ' right( commas(ills), 9) say ' number of duplicate words in the dictionary: ' right( commas(dups), 9) say ' number of acceptable words in the dictionary: ' right( commas(wrds), 9) say ' the "word" to be used for text completion: ' what say call del what; a= a result; call del what,1; a= a result call ins what; a= a result; call ins what,1; a= a result call sub what; a= a result; call sub what,1; a= a result call prune
- = words($)
say commas(#) ' similar words found:'
do j=1 for #; _= word($, j); say right( count(_,what), 24) _ end /*j*/
exit # /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do ?=length(_)-3 to 1 by -3; _= insert(',', _, ?); end; return _ prune: do k=1 for words(a); _= word(a,k); if wordpos(_,$)==0 then $= $ _; end; return recur: $= $ del(z); $= $ ins(z); $= $ sub(z); return /*──────────────────────────────────────────────────────────────────────────────────────*/ count: procedure; parse arg x,y; cnt= 0; w= length(x)
do j=1 for w; p= pos( substr(x, j, 1), y); if p==0 then iterate y= overlay(., y, p); cnt= cnt + 1 end /*j*/ return ' ' left("("format(cnt/w*100,,2)/1'%)', 9) /*express as a percent.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/ del: procedure expose @. @abc L; parse arg y,r; $=
do j=1 for length(y); z= space(left(y,j-1) || substr(y,j+1), 0) if @.z\==. then $= $ z; if r==1 then call recur end /*j*/; return space($)
/*──────────────────────────────────────────────────────────────────────────────────────*/ ins: procedure expose @. @abc L; parse arg y,r; $=
do j=1 for length(y) do k=1 for L; z= space(left(y,j-1) || substr(@abc,k,1) || substr(y,j), 0) if @.z\==. then $= $ z; if r==1 then call recur end /*k*/ end /*j*/; return space($)
/*──────────────────────────────────────────────────────────────────────────────────────*/ sub: procedure expose @. @abc L; parse arg y,r; $=
do j=1 for length(y) do k=1 for L; z= space(left(y,j-1) || substr(@abc,k,1) || substr(y,j+1), 0) if @.z\==. then $= $ z; if r==1 then call recur end /*k*/ end /*j*/; return space($)</lang>
- output when using the default inputs:
Reading the file: UNIXDICT.TXT number of records (words) in the dictionary: 25,104 number of ill─formed words in the dictionary: 126 number of duplicate words in the dictionary: 0 number of acceptable words in the dictionary: 24,978 the "word" to be used for text completion: complition 6 similar words found: (88.89%) coalition (90%) completion (81.82%) competition (90.91%) compilation (81.82%) composition (80%) complexion
The input file is the same dictionary that the Java entry used.
- output when using the inputs of: , GitHub.dict
Reading the file: GitHub.dict number of records (words) in the dictionary: 466,551 number of ill─formed words in the dictionary: 50,254 number of duplicate words in the dictionary: 0 number of acceptable words in the dictionary: 416,297 the "word" to be used for text completion: complition 11 similar words found: (88.89%) coalition (90%) completion (81.82%) commolition (81.82%) comparition (81.82%) competition (90.91%) compilation (81.82%) composition (81.82%) complection (83.33%) complication (80%) compaction (80%) complexion
Wren
This uses 'unixdict' and the Levenshtein distance algorithm to test for similarity. <lang ecmascript>import "io" for File import "/fmt" for Fmt
var levenshtein = Fn.new { |s, t|
var ls = s.count var lt = t.count var d = List.filled(ls + 1, null) for (i in 0..ls) { d[i] = List.filled(lt + 1, 0) d[i][0] = i } for (j in 0..lt) d[0][j] = j for (j in 1..lt) { for (i in 1..ls) { if (s[i-1] == t[j-1]) { d[i][j] = d[i-1][j-1] } else { var min = d[i-1][j] if (d[i][j-1] < min) min = d[i][j-1] if (d[i-1][j-1] < min) min = d[i-1][j-1] d[i][j] = min + 1 } } } return d[-1][-1]
}
var search = "complition" var words = File.read("unixdict.txt").split("\n").map { |w| w.trim() }.where { |w| w != "" } var lev = [[], [], [], []] var ld for (word in words) {
if ((ld = levenshtein.call(search, word)) < 4) { lev[ld].add(word) }
}
System.print("Input word: %(search)\n") for (i in 1..3) {
var count = search.count var similarity = (count - i) * 100 / count Fmt.print("Words which are $4.1f\% similar:", similarity) System.print(lev[i]) System.print()
} </lang>
- Output:
Words which are 90.0% similar: [completion] Words which are 80.0% similar: [coalition, competition, compilation, complexion, composition] Words which are 70.0% similar: [cognition, collision, combustion, commotion, companion, compassion, complain, complicity, compton, compulsion, compunction, computation, condition, contrition, demolition, incompletion, volition]