Skip to content

Commit 63af415

Browse files
shuvavashuvava
committed
add fuzzy strings exmaples
1 parent d6fe2d8 commit 63af415

6 files changed

Lines changed: 266 additions & 42 deletions

File tree

‎DynamicProgramming/README.md‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
# Dynamic Programming
2+
3+
Dynamic programming (DP) is
4+
5+
* careful brute force
6+
* divide to subproblems + reuse solution of these subproblems
7+
* subporblems should not have cyclic dependencies
8+
9+
## Memoize
10+
11+
**memoize** - (remember) & re-use solutions to subproblems that help solve problem
12+
13+
## bottom-up
14+
15+
idea of algorithm is start solving program from bottom and go up, may uses in junction with memoize
16+
17+
## Guessing
18+
19+
try all possible ways of solving subproblem and choose the best one.
20+
21+
## Logical step of using DP
22+
23+
1. define subproblem (for recursion) = find exactly same computation
24+
1. guess (part of solution)
25+
1. topological sort of subproblem dependency DAG
26+
1. build algorithm memoize && (recursive || build DP table bottom-up)
27+
1. try to find ways to save space(memory)
28+
1. solve original problem

‎DynamicProgramming/fibonacci.py‎

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
#!/usr/bin/env python
2+
# encoding: utf-8
3+
#
4+
# Copyright (c) 2019 Vladimir Shurygin. All rights reserved.
5+
#
6+
'''
7+
Given an integer n, write a function to compute the nth Fibonacci number.
8+
'''
9+
import argparse
10+
import random
11+
12+
def fibonacci(n):
13+
'''it is naive implementation which takes exponential time to execute.
14+
BigO=2**(n/2)
15+
'''
16+
if n <= 1:
17+
return 1
18+
n0 = 0
19+
n1 = 1
20+
result = 1
21+
level = 2
22+
while level <= n:
23+
result = n0 + n1
24+
n0 = n1
25+
n1 = result
26+
level += 1
27+
return result
28+
29+
_MEMO = {}
30+
def fibonacci_with_hash(n):
31+
'''
32+
it use memoize dynamic programming algorithm
33+
BigO = n
34+
'''
35+
if n in _MEMO:
36+
return _MEMO[n]
37+
if n <= 2:
38+
return 1
39+
f = fibonacci_with_hash(n-1) + fibonacci_with_hash(n-2)
40+
_MEMO[n] = f
41+
return f
42+
43+
44+
def fib_bottom_up(n):
45+
'''
46+
dynamic programming bottom-up algorithm
47+
idea of algorithm is start solving program from bottom and go up,
48+
may uses in junction with memoize DP
49+
it use array as a cache
50+
BigO = n
51+
'''
52+
_memo = [1]*n #init array
53+
fib = 1
54+
for arr_inx in range(0, n):
55+
if arr_inx <= 1:
56+
fib = 1
57+
else:
58+
fib = _memo[arr_inx-1] + _memo[arr_inx-2]
59+
_memo[arr_inx] = fib
60+
return fib
61+
62+
def get_context():
63+
''' Create execution context command line args
64+
Returns
65+
-------
66+
Object
67+
object with command line arguments '''
68+
parser = argparse.ArgumentParser()
69+
parser.add_argument("-n", "--number",\
70+
help="fibonacci level",\
71+
dest="number", type=int, default=random.randrange(0, 24))
72+
return parser.parse_args()
73+
74+
if __name__ == '__main__':
75+
context = get_context()
76+
level = context.number
77+
result = fibonacci(level)
78+
print(f'fibonacci({level}) = {result}')
79+
result = fib_bottom_up(level)
80+
print(f'fibonacci({level}) = {result}')

‎fuzzy-string/autocorection-markov-chain.py‎

Lines changed: 76 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +1,76 @@
1-
#https://yurichev.com/blog/markov/
1+
#!/usr/bin/env python
2+
# encoding: utf-8
3+
#
4+
# Copyright (c) 2019 Vladimir Shurygin. All rights reserved.
5+
# was stollen from https://yurichev.com/blog/markov/
6+
7+
import re
8+
from collections import Counter
9+
from zipfile import ZipFile
10+
11+
FIRST = {}
12+
SECOND = {}
13+
THIRD = {}
14+
15+
def update_word_occurrence(word_dict, prefix, word):
16+
if prefix not in word_dict:
17+
word_dict[prefix] = Counter()
18+
word_dict[prefix].update([word])
19+
20+
with ZipFile('big.zip') as archive, archive.open('big.txt', 'r') as f:
21+
#https://stackoverflow.com/questions/25735644/python-regex-for-splitting-text-into-sentences-sentence-tokenizing
22+
SENTENCES = re.split(r'(?<!\w\.\w.)(?<![A-Z][a-z]\.)(?<=\.|\?)\s', f.read().decode('utf-8'))
23+
for sentence in SENTENCES:
24+
words = re.findall(r'\w+', sentence.lower())
25+
if len(words) == 0:
26+
continue
27+
for i in range(len(words)):
28+
if i >= 1:
29+
update_word_occurrence(FIRST, words[i-1], words[i])
30+
if i >= 2:
31+
update_word_occurrence(SECOND, f'{words[i-2]} {words[i-1]}', words[i])
32+
if i >= 3:
33+
update_word_occurrence(THIRD, f'{words[i-3]} {words[i-2]} {words[i-1]}', words[i])
34+
35+
def print_stat(t):
36+
total=float(sum(t.values()))
37+
for pair in t.most_common(5):
38+
print ('%s %d%%' % (pair[0], (float(pair[1])/total)*100))
39+
40+
41+
if __name__ == '__main__':
42+
test='i can tell'
43+
#test='who did this'
44+
#test='she was a'
45+
#test='he was a'
46+
#test='i did not'
47+
#test='all that she'
48+
#test='have not been'
49+
#test='who wanted to'
50+
#test='he wanted to'
51+
#test='wanted to do'
52+
#test='it is just'
53+
#test='you will find'
54+
#test='you shall'
55+
#test='proved to be'
56+
test_words=test.split(' ')
57+
test_len=len(test_words)
58+
last_idx=test_len-1
59+
if test_len>=3:
60+
tmp=test_words[last_idx-2]+' '+test_words[last_idx-1]+' '+test_words[last_idx]
61+
if tmp in THIRD:
62+
print('* third order. for sequence:',tmp)
63+
print_stat(THIRD[tmp])
64+
65+
if test_len>=2:
66+
tmp=test_words[last_idx-1]+' '+test_words[last_idx]
67+
if tmp in SECOND:
68+
print('* second order. for sequence:', tmp)
69+
print_stat(SECOND[tmp])
70+
71+
if test_len>=1:
72+
tmp=test_words[last_idx]
73+
if tmp in FIRST:
74+
print('* first order. for word:', tmp)
75+
print_stat(FIRST[tmp])
76+
print('')

fuzzy-string/autocorrection-levenshtein-distance.py renamed to fuzzy-string/autocorrection_levenshtein_distance.py

Lines changed: 26 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -6,33 +6,45 @@
66
# source code from https://github.com/norvig/pytudes
77
#https://yurichev.com/blog/fuzzy_string/
88

9+
'''
10+
The Levenshtein distance is a string metric for measuring difference between two
11+
sequences. Informally, the Levenshtein distance between two words is
12+
the minimum number of single-character edits
13+
(i.e. insertions, deletions or substitutions)
14+
required to change one word into the other.
15+
'''
16+
917
################ Spelling Corrector
1018

1119
import re
1220
from collections import Counter
21+
from zipfile import ZipFile
22+
23+
words = lambda text: re.findall(r'\w+', text.lower())
1324

14-
def words(text): return re.findall(r'\w+', text.lower())
25+
with ZipFile('big.zip') as archive, archive.open('big.txt', 'r') as f:
26+
WORDS = Counter(words(f.read().decode('utf-8')))
1527

16-
WORDS = Counter(words(open('big.txt').read()))
28+
COUNT_OF_WORDS = sum(WORDS.values())
1729

18-
def P(word, N=sum(WORDS.values())):
19-
"Probability of `word`."
30+
def P(word, N=COUNT_OF_WORDS):
31+
'Probability of `word`.'
2032
return WORDS[word] / N
2133

22-
def correction(word):
23-
"Most probable spelling correction for word."
34+
def correction(word):
35+
'Most probable spelling correction for word.'
2436
return max(candidates(word), key=P)
2537

26-
def candidates(word):
27-
"Generate possible spelling corrections for word."
38+
def candidates(word):
39+
'Generate possible spelling corrections for word.'
2840
return (known([word]) or known(edits1(word)) or known(edits2(word)) or [word])
2941

30-
def known(words):
31-
"The subset of `words` that appear in the dictionary of WORDS."
42+
def known(words):
43+
'The subset of `words` that appear in the dictionary of WORDS.'
3244
return set(w for w in words if w in WORDS)
3345

3446
def edits1(word):
35-
"All edits that are one edit away from `word`."
47+
'All edits that are one edit away from `word`.'
3648
letters = 'abcdefghijklmnopqrstuvwxyz'
3749
splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
3850
deletes = [L + R[1:] for L, R in splits if R]
@@ -41,8 +53,8 @@ def edits1(word):
4153
inserts = [L + c + R for L, R in splits for c in letters]
4254
return set(deletes + transposes + replaces + inserts)
4355

44-
def edits2(word):
45-
"All edits that are two edits away from `word`."
56+
def edits2(word):
57+
'All edits that are two edits away from `word`.'
4658
return (e2 for e1 in edits1(word) for e2 in edits1(e1))
4759

4860
## To rewrite
@@ -62,7 +74,7 @@ def unit_tests():
6274
assert Counter(words('This is a test. 123; A TEST this is.')) == (
6375
Counter({'123': 1, 'a': 2, 'is': 2, 'test': 2, 'this': 2}))
6476
assert len(WORDS) == 32198
65-
assert sum(WORDS.values()) == 1115585
77+
assert COUNT_OF_WORDS == 1115585
6678
assert WORDS.most_common(10) == [
6779
('the', 79809),
6880
('of', 40024),
@@ -79,31 +91,5 @@ def unit_tests():
7991
assert 0.07 < P('the') < 0.08
8092
return 'unit_tests pass'
8193

82-
def spelltest(tests, verbose=False):
83-
"Run correction(wrong) on all (right, wrong) pairs; report results."
84-
import time
85-
start = time.clock()
86-
good, unknown = 0, 0
87-
n = len(tests)
88-
for right, wrong in tests:
89-
w = correction(wrong)
90-
good += (w == right)
91-
if w != right:
92-
unknown += (right not in WORDS)
93-
if verbose:
94-
print('correction({}) => {} ({}); expected {} ({})'
95-
.format(wrong, w, WORDS[w], right, WORDS[right]))
96-
dt = time.clock() - start
97-
print('{:.0%} of {} correct ({:.0%} unknown) at {:.0f} words per second '
98-
.format(good / n, n, unknown / n, n / dt))
99-
100-
def Testset(lines):
101-
"Parse 'right: wrong1 wrong2' lines into [('right', 'wrong1'), ('right', 'wrong2')] pairs."
102-
return [(right, wrong)
103-
for (right, wrongs) in (line.split(':') for line in lines)
104-
for wrong in wrongs.split()]
105-
10694
if __name__ == '__main__':
10795
print(unit_tests())
108-
spelltest(Testset(open('spell-testset1.txt')))
109-
spelltest(Testset(open('spell-testset2.txt')))

‎fuzzy-string/textgenerator-markov-chain.py‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
#!/usr/bin/env python
2+
# encoding: utf-8
3+
#
4+
# Copyright (c) 2019 Vladimir Shurygin. All rights reserved.
5+
# was stollen from https://yurichev.com/blog/markov/
6+
7+
import random
8+
import re
9+
from collections import Counter
10+
from zipfile import ZipFile
11+
12+
FIRST = {}
13+
SECOND = {}
14+
15+
def update_word_occurrence(word_dict, prefix, word):
16+
if prefix not in word_dict:
17+
word_dict[prefix] = Counter()
18+
word_dict[prefix].update([word])
19+
20+
with ZipFile('big.zip') as archive, archive.open('big.txt', 'r') as f:
21+
#https://stackoverflow.com/questions/25735644/python-regex-for-splitting-text-into-sentences-sentence-tokenizing
22+
SENTENCES = re.split(r'(?<!\w\.\w.)(?<![A-Z][a-z]\.)(?<=\.|\?)\s', f.read().decode('utf-8'))
23+
for sentence in SENTENCES:
24+
words = re.findall(r'\w+', sentence.lower())
25+
if len(words)==0:
26+
continue
27+
for i in range(len(words)):
28+
if i >= 1:
29+
update_word_occurrence(FIRST, words[i-1], words[i])
30+
if i >= 2:
31+
update_word_occurrence(SECOND, f'{words[i-2]} {words[i-1]}', words[i])
32+
33+
def gen_random_from_tbl(t):
34+
# https://docs.python.org/3/library/random.html#random.choice
35+
return random.choices(list(t.keys()), weights=list(t.values()))[0]
36+
37+
if __name__ == '__main__':
38+
text=["it", "is"]
39+
text_len=len(text)
40+
# generate at most 200 words:
41+
for i in range(200):
42+
last_idx=text_len-1
43+
tmp=text[last_idx-1]+" "+text[last_idx]
44+
if tmp in SECOND:
45+
new_word=gen_random_from_tbl(SECOND[tmp])
46+
else:
47+
# fall-back to 1st order
48+
tmp2=text[last_idx]
49+
if tmp2 not in FIRST:
50+
# dead-end
51+
break
52+
new_word=gen_random_from_tbl(FIRST[tmp2])
53+
text.append(new_word)
54+
text_len=text_len+1
55+
print (' '.join(text))

‎sort/counting_v2.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@ def sort(_array, length, val_range):
1414
for key in range(length):
1515
item = _keys[_array[key]]
1616
if not item:
17-
_keys[_array[key]] = [_array[key]]
17+
_keys[_array[key]] = [_array[key]]
1818
else:
1919
item.append(_array[key])
2020
result = []

0 commit comments

Comments
 (0)