]> gitweb.factorcode.org Git - factor.git/commitdiff
spelling: John Benediktsson's port of Peter Norvig's spelling corrector
authorSlava Pestov <slava@slava-pestovs-macbook-pro.local>
Sat, 27 Mar 2010 10:25:47 +0000 (06:25 -0400)
committerSlava Pestov <slava@slava-pestovs-macbook-pro.local>
Sat, 27 Mar 2010 10:25:47 +0000 (06:25 -0400)
extra/spelling/authors.txt [new file with mode: 0644]
extra/spelling/spelling-tests.factor [new file with mode: 0644]
extra/spelling/spelling.factor [new file with mode: 0644]
extra/spelling/summary.txt [new file with mode: 0644]
extra/spelling/tags.txt [new file with mode: 0644]
extra/spelling/test.txt [new file with mode: 0644]

diff --git a/extra/spelling/authors.txt b/extra/spelling/authors.txt
new file mode 100644 (file)
index 0000000..e091bb8
--- /dev/null
@@ -0,0 +1 @@
+John Benediktsson
diff --git a/extra/spelling/spelling-tests.factor b/extra/spelling/spelling-tests.factor
new file mode 100644 (file)
index 0000000..f323638
--- /dev/null
@@ -0,0 +1,14 @@
+USING: spelling tools.test memoize ;
+IN: spelling.tests
+
+MEMO: test-dictionary ( -- assoc )
+    "vocab:spelling/test.txt" load-dictionary ;
+
+: test-correct ( word -- word/f )
+    test-dictionary (correct) ;
+
+[ "government" ] [ "goverment" test-correct ] unit-test
+[ "government" ] [ "govxernment" test-correct ] unit-test
+[ "government" ] [ "govermnent" test-correct ] unit-test
+[ "government" ] [ "govxermnent" test-correct ] unit-test
+[ "government" ] [ "govyrmnent" test-correct ] unit-test
diff --git a/extra/spelling/spelling.factor b/extra/spelling/spelling.factor
new file mode 100644 (file)
index 0000000..b8a90bd
--- /dev/null
@@ -0,0 +1,78 @@
+USING: arrays ascii assocs combinators combinators.smart fry
+http.client io.encodings.ascii io.files io.files.temp kernel
+locals math math.statistics memoize sequences sorting splitting
+strings urls ;
+IN: spelling
+
+! http://norvig.com/spell-correct.html
+
+CONSTANT: ALPHABET "abcdefghijklmnopqrstuvwxyz"
+
+: splits ( word -- sequence )
+    dup length iota [ cut 2array ] with map ;
+
+: deletes ( sequence -- sequence' )
+    [ second length 0 > ] filter [ first2 rest append ] map ;
+
+: transposes ( sequence -- sequence' )
+    [ second length 1 > ] filter [
+        [
+            {
+                [ first ]
+                [ second second 1string ]
+                [ second first 1string ]
+                [ second 2 tail ]
+            } cleave
+        ] "" append-outputs-as
+    ] map ;
+
+: replaces ( sequence -- sequence' )
+    [ second length 0 > ] filter [
+        [ ALPHABET ] dip first2
+        '[ 1string _ _ rest surround ] { } map-as
+    ] map concat ;
+
+: inserts ( sequence -- sequence' )
+    [
+        ALPHABET
+        [ [ first2 ] dip 1string glue ] with { } map-as
+    ] map concat ;
+
+: edits1 ( word -- edits )
+    [
+        splits {
+            [ deletes ]
+            [ transposes ]
+            [ replaces ]
+            [ inserts ]
+        } cleave
+    ] append-outputs ;
+
+: edits2 ( word -- edits )
+    edits1 [ edits1 ] map concat ;
+
+: filter-known ( words dictionary -- words' )
+    '[ _ key? ] filter ;
+
+:: corrections ( word dictionary -- words )
+    word 1array dictionary filter-known
+    [ word edits1 dictionary filter-known ] when-empty
+    [ word edits2 dictionary filter-known ] when-empty
+    [ dictionary at 1 or ] sort-with ;
+
+: words ( string -- words )
+    >lower [ letter? not ] split-when harvest ;
+
+: load-dictionary ( file -- assoc )
+    ascii file-contents words histogram ;
+
+MEMO: default-dictionary ( -- counts )
+    "big.txt" temp-file dup exists?
+    [ URL" http://norvig.com/big.txt" over download-to ] unless
+    load-dictionary ;
+
+: (correct) ( word dictionary -- word/f )
+    corrections [ f ] [ first ] if-empty ;
+
+: correct ( word -- word/f )
+    default-dictionary (correct) ;
diff --git a/extra/spelling/summary.txt b/extra/spelling/summary.txt
new file mode 100644 (file)
index 0000000..7fa9068
--- /dev/null
@@ -0,0 +1 @@
+Peter Norvig's spelling corrector
diff --git a/extra/spelling/tags.txt b/extra/spelling/tags.txt
new file mode 100644 (file)
index 0000000..1e107f5
--- /dev/null
@@ -0,0 +1 @@
+examples
diff --git a/extra/spelling/test.txt b/extra/spelling/test.txt
new file mode 100644 (file)
index 0000000..5b9de09
--- /dev/null
@@ -0,0 +1,246 @@
+AMERICAN FOREIGN RELATIONS (1865-98)
+
+=French Intrigues in Mexico Blocked.=--Between the war for the union and
+the war with Spain, the Department of State had many an occasion to
+present the rights of America among the powers of the world. Only a
+little while after the civil conflict came to a close, it was called
+upon to deal with a dangerous situation created in Mexico by the
+ambitions of Napoleon III. During the administration of Buchanan, Mexico
+had fallen into disorder through the strife of the Liberal and the
+Clerical parties; the President asked for authority to use American
+troops to bring to a peaceful haven "a wreck upon the ocean, drifting
+about as she is impelled by different factions." Our own domestic crisis
+then intervened.
+
+Observing the United States heavily involved in its own problems, the
+great powers, England, France, and Spain, decided in the autumn of 1861
+to take a hand themselves in restoring order in Mexico. They entered
+into an agreement to enforce the claims of their citizens against Mexico
+and to protect their subjects residing in that republic. They invited
+the United States to join them, and, on meeting a polite refusal, they
+prepared for a combined military and naval demonstration on their own
+account. In the midst of this action England and Spain, discovering the
+sinister purposes of Napoleon, withdrew their troops and left the field
+to him.
+
+The French Emperor, it was well known, looked with jealousy upon the
+growth of the United States and dreamed of establishing in the Western
+hemisphere an imperial power to offset the American republic.
+Intervention to collect debts was only a cloak for his deeper designs.
+Throwing off that guise in due time, he made the Archduke Maximilian, a
+brother of the ruler of Austria, emperor in Mexico, and surrounded his
+throne by French soldiers, in spite of all protests.
+
+This insolent attack upon the Mexican republic, deeply resented in the
+United States, was allowed to drift in its course until 1865. At that
+juncture General Sheridan was dispatched to the Mexican border with a
+large armed force; General Grant urged the use of the American army to
+expel the French from this continent. The Secretary of State, Seward,
+counseled negotiation first, and, applying the Monroe Doctrine, was able
+to prevail upon Napoleon III to withdraw his troops. Without the support
+of French arms, the sham empire in Mexico collapsed like a house of
+cards and the unhappy Maximilian, the victim of French ambition and
+intrigue, met his death at the hands of a Mexican firing squad.
+
+=Alaska Purchased.=--The Mexican affair had not been brought to a close
+before the Department of State was busy with negotiations which resulted
+in the purchase of Alaska from Russia. The treaty of cession, signed on
+March 30, 1867, added to the United States a domain of nearly six
+hundred thousand square miles, a territory larger than Texas and nearly
+three-fourths the size of the Louisiana purchase. Though it was a
+distant colony separated from our continental domain by a thousand miles
+of water, no question of "imperialism" or "colonization foreign to
+American doctrines" seems to have been raised at the time. The treaty
+was ratified promptly by the Senate. The purchase price, $7,200,000, was
+voted by the House of Representatives after the display of some
+resentment against a system that compelled it to appropriate money to
+fulfill an obligation which it had no part in making. Seward, who
+formulated the treaty, rejoiced, as he afterwards said, that he had kept
+Alaska out of the hands of England.
+
+=American Interest in the Caribbean.=--Having achieved this diplomatic
+triumph, Seward turned to the increase of American power in another
+direction. He negotiated, with Denmark, a treaty providing for the
+purchase of the islands of St. John and St. Thomas in the West Indies,
+strategic points in the Caribbean for sea power. This project, long
+afterward brought to fruition by other men, was defeated on this
+occasion by the refusal of the Senate to ratify the treaty. Evidently it
+was not yet prepared to exercise colonial dominion over other races.
+
+Undaunted by the misadventure in Caribbean policies, President Grant
+warmly advocated the acquisition of Santo Domingo. This little republic
+had long been in a state of general disorder. In 1869 a treaty of
+annexation was concluded with its president. The document Grant
+transmitted to the Senate with his cordial approval, only to have it
+rejected. Not at all changed in his opinion by the outcome of his
+effort, he continued to urge the subject of annexation. Even in his last
+message to Congress he referred to it, saying that time had only proved
+the wisdom of his early course. The addition of Santo Domingo to the
+American sphere of protection was the work of a later generation. The
+State Department, temporarily checked, had to bide its time.
+
+=The _Alabama_ Claims Arbitrated.=--Indeed, it had in hand a far more
+serious matter, a vexing issue that grew out of Civil War diplomacy. The
+British government, as already pointed out in other connections, had
+permitted Confederate cruisers, including the famous _Alabama_, built in
+British ports, to escape and prey upon the commerce of the Northern
+states. This action, denounced at the time by our government as a grave
+breach of neutrality as well as a grievous injury to American citizens,
+led first to remonstrances and finally to repeated claims for damages
+done to American ships and goods. For a long time Great Britain was
+firm. Her foreign secretary denied all obligations in the premises,
+adding somewhat curtly that "he wished to say once for all that Her
+Majesty's government disclaimed any responsibility for the losses and
+hoped that they had made their position perfectly clear." Still
+President Grant was not persuaded that the door of diplomacy, though
+closed, was barred. Hamilton Fish, his Secretary of State, renewed the
+demand. Finally he secured from the British government in 1871 the
+treaty of Washington providing for the arbitration not merely of the
+_Alabama_ and other claims but also all points of serious controversy
+between the two countries.
+
+The tribunal of arbitration thus authorized sat at Geneva in
+Switzerland, and after a long and careful review of the arguments on
+both sides awarded to the United States the lump sum of $15,500,000 to
+be distributed among the American claimants. The damages thus allowed
+were large, unquestionably larger than strict justice required and it is
+not surprising that the decision excited much adverse comment in
+England. Nevertheless, the prompt payment by the British government
+swept away at once a great cloud of ill-feeling in America. Moreover,
+the spectacle of two powerful nations choosing the way of peaceful
+arbitration to settle an angry dispute seemed a happy, if illusory, omen
+of a modern method for avoiding the arbitrament of war.
+
+=Samoa.=--If the Senate had its doubts at first about the wisdom of
+acquiring strategic points for naval power in distant seas, the same
+could not be said of the State Department or naval officers. In 1872
+Commander Meade, of the United States navy, alive to the importance of
+coaling stations even in mid-ocean, made a commercial agreement with the
+chief of Tutuila, one of the Samoan Islands, far below the equator, in
+the southern Pacific, nearer to Australia than to California. This
+agreement, providing among other things for our use of the harbor of
+Pago Pago as a naval base, was six years later changed into a formal
+treaty ratified by the Senate.
+
+Such enterprise could not escape the vigilant eyes of England and
+Germany, both mindful of the course of the sea power in history. The
+German emperor, seizing as a pretext a quarrel between his consul in the
+islands and a native king, laid claim to an interest in the Samoan
+group. England, aware of the dangers arising from German outposts in the
+southern seas so near to Australia, was not content to stand aside. So
+it happened that all three countries sent battleships to the Samoan
+waters, threatening a crisis that was fortunately averted by friendly
+settlement. If, as is alleged, Germany entertained a notion of
+challenging American sea power then and there, the presence of British
+ships must have dispelled that dream.
+
+The result of the affair was a tripartite agreement by which the three
+powers in 1889 undertook a protectorate over the islands. But joint
+control proved unsatisfactory. There was constant friction between the
+Germans and the English. The spheres of authority being vague and open
+to dispute, the plan had to be abandoned at the end of ten years.
+England withdrew altogether, leaving to Germany all the islands except
+Tutuila, which was ceded outright to the United States. Thus one of the
+finest harbors in the Pacific, to the intense delight of the American
+navy, passed permanently under American dominion. Another triumph in
+diplomacy was set down to the credit of the State Department.
+
+=Cleveland and the Venezuela Affair.=--In the relations with South
+America, as well as in those with the distant Pacific, the diplomacy of
+the government at Washington was put to the test. For some time it had
+been watching a dispute between England and Venezuela over the western
+boundary of British Guiana and, on an appeal from Venezuela, it had
+taken a lively interest in the contest. In 1895 President Cleveland saw
+that Great Britain would yield none of her claims. After hearing the
+arguments of Venezuela, his Secretary of State, Richard T. Olney, in a
+note none too conciliatory, asked the British government whether it was
+willing to arbitrate the points in controversy. This inquiry he
+accompanied by a warning to the effect that the United States could not
+permit any European power to contest its mastery in this hemisphere.
+"The United States," said the Secretary, "is practically sovereign on
+this continent and its fiat is law upon the subjects to which it
+confines its interposition.... Its infinite resources, combined with its
+isolated position, render it master of the situation and practically
+invulnerable against any or all other powers."
+
+The reply evoked from the British government by this strong statement
+was firm and clear. The Monroe Doctrine, it said, even if not so widely
+stretched by interpretation, was not binding in international law; the
+dispute with Venezuela was a matter of interest merely to the parties
+involved; and arbitration of the question was impossible. This response
+called forth President Cleveland's startling message of 1895. He asked
+Congress to create a commission authorized to ascertain by researches
+the true boundary between Venezuela and British Guiana. He added that it
+would be the duty of this country "to resist by every means in its
+power, as a willful aggression upon its rights and interests, the
+appropriation by Great Britain of any lands or the exercise of
+governmental jurisdiction over any territory which, after investigation,
+we have determined of right belongs to Venezuela." The serious character
+of this statement he thoroughly understood. He declared that he was
+conscious of his responsibilities, intimating that war, much as it was
+to be deplored, was not comparable to "a supine submission to wrong and
+injustice and the consequent loss of national self-respect and honor."
+
+[Illustration: GROVER CLEVELAND]
+
+The note of defiance which ran through this message, greeted by shrill
+cries of enthusiasm in many circles, was viewed in other quarters as a
+portent of war. Responsible newspapers in both countries spoke of an
+armed settlement of the dispute as inevitable. Congress created the
+commission and appropriated money for the investigation; a body of
+learned men was appointed to determine the merits of the conflicting
+boundary claims. The British government, deaf to the clamor of the
+bellicose section of the London press, deplored the incident,
+courteously replied in the affirmative to a request for assistance in
+the search for evidence, and finally agreed to the proposition that the
+issue be submitted to arbitration. The outcome of this somewhat perilous
+dispute contributed not a little to Cleveland's reputation as "a
+sterling representative of the true American spirit." This was not
+diminished when the tribunal of arbitration found that Great Britain was
+on the whole right in her territorial claims against Venezuela.
+
+=The Annexation of Hawaii.=--While engaged in the dangerous Venezuela
+controversy, President Cleveland was compelled by a strange turn in
+events to consider the annexation of the Hawaiian Islands in the
+mid-Pacific. For more than half a century American missionaries had been
+active in converting the natives to the Christian faith and enterprising
+American business men had been developing the fertile sugar plantations.
+Both the Department of State and the Navy Department were fully
+conscious of the strategic relation of the islands to the growth of sea
+power and watched with anxiety any developments likely to bring them
+under some other Dominion.
+
+The country at large was indifferent, however, until 1893, when a
+revolution, headed by Americans, broke out, ending in the overthrow of
+the native government, the abolition of the primitive monarchy, and the
+retirement of Queen Liliuokalani to private life. This crisis, a
+repetition of the Texas affair in a small theater, was immediately
+followed by a demand from the new Hawaiian government for annexation to
+the United States. President Harrison looked with favor on the proposal,
+negotiated the treaty of annexation, and laid it before the Senate for
+approval. There it still rested when his term of office was brought to a
+close.
+
+Harrison's successor, Cleveland, it was well known, had doubts about the
+propriety of American action in Hawaii. For the purpose of making an
+inquiry into the matter, he sent a special commissioner to the islands.
+On the basis of the report of his agent, Cleveland came to the
+conclusion that "the revolution in the island kingdom had been
+accomplished by the improper use of the armed forces of the United
+States and that the wrong should be righted by a restoration of the
+queen to her throne." Such being his matured conviction, though the
+facts upon which he rested it were warmly controverted, he could do
+nothing but withdraw the treaty from the Senate and close the incident.
+
+To the Republicans this sharp and cavalier disposal of their plans,
+carried out in a way that impugned the motives of a Republican
+President, was nothing less than "a betrayal of American interests." In
+their platform of 1896 they made clear their position: "Our foreign
+policy should be at all times firm, vigorous, and dignified and all our
+interests in the Western hemisphere carefully watched and guarded. The
+Hawaiian Islands should be controlled by the United States and no
+foreign power should be permitted to interfere with them." There was no
+mistaking this view of the issue. As the vote in the election gave
+popular sanction to Republican policies, Congress by a joint resolution,
+passed on July 6, 1898, annexed the islands to the United States and
+later conferred upon them the ordinary territorial form of government.