Spaces:
Sleeping
Sleeping
| import gradio as gr | |
| # please check the course slides to get much simpler implementation | |
| def get_pm_table(pattern): | |
| L = len(pattern) | |
| pm = [0]*L | |
| k = 0 | |
| for q in range(1,L): | |
| if pattern[q] == pattern[k]: | |
| pm[q] = k + 1 | |
| k = k + 1 | |
| else: | |
| while k > 0: | |
| k = pm[k-1] | |
| if pattern[k] == pattern[q]: | |
| pm[q] = k + 1 | |
| k = k + 1 | |
| break | |
| if k == 0: | |
| if pattern[q] == pattern[k]: | |
| pm[q] = k + 1 | |
| k = k + 1 | |
| else: | |
| pm[q] = 0 | |
| return pm | |
| def KMP_search(pattern, string): | |
| m = len(pattern) | |
| n = len(string) | |
| pm = get_pm_table(pattern) | |
| i = 0 | |
| q = 0 | |
| location = [] | |
| trial = 0 | |
| while i < n: | |
| if string[i] == pattern[q]: | |
| i = i + 1 | |
| q = q + 1 | |
| if q == m: | |
| pos = i - q | |
| q = pm[q-1] | |
| location.append(pos+1)# set index starting from 1 | |
| #print("Found ", string[pos:pos+m], ' locating at position ', location) | |
| else: | |
| if q ==0: | |
| i = i + 1 | |
| trial += 1 | |
| #print(trial,"-> i=",i) | |
| #print(string[i:i+m]) | |
| #print(pattern) | |
| else: | |
| q = pm[q-1] | |
| return location | |
| def search_pattern(fulltext, pattern, method): | |
| fulltext = fulltext.replace('\n','') | |
| pattern = pattern.replace('\n','') | |
| if method == 'Naive-Exact-Match': | |
| import time | |
| start = time.time() | |
| occurrence = 0 | |
| for i in range(0,len(fulltext)-len(pattern)+1): | |
| found = 1 | |
| for l in range(len(pattern)): | |
| if fulltext[i+l] != pattern[l]: | |
| found = 0 | |
| if found: | |
| occurrence += 1 | |
| print("Found ", fulltext[i:i+len(pattern)], ' locating at position ', i+1) | |
| end = time.time() | |
| time_elapse = end - start | |
| if method == "Knuth-Morris-Pratt": | |
| import time | |
| start = time.time() | |
| results = KMP_search(pattern, fulltext) | |
| end = time.time() | |
| time_elapse = end - start | |
| occurrence = len(results) | |
| return occurrence, time_elapse | |
| ### configure inputs/outputs | |
| set_fulltext = gr.inputs.Textbox(label="Full Text") | |
| set_pattern = gr.inputs.Textbox(label="Pattern") | |
| set_method = gr.Radio(["Naive-Exact-Match", "Knuth-Morris-Pratt"]) | |
| set_results = gr.outputs.Textbox(label="Occurrence") | |
| set_times = gr.outputs.Textbox(label="Time elapse") | |
| ### configure gradio, detailed can be found at https://www.gradio.app/docs/#i_slider | |
| interface = gr.Interface(fn=search_pattern, | |
| inputs=[set_fulltext, set_pattern,set_method], | |
| outputs=[set_results,set_times], | |
| examples_per_page = 2, | |
| title="BCB5300 Demo 1: Sequence Match", | |
| theme = 'huggingface', | |
| layout = 'vertical' | |
| ) | |
| interface.launch(debug=True) |