Pytania otagowane jako strings

Pytania o ciągi symboli, ich zestawy i ich właściwości, a także zastosowania.

2
Wydajne struktury danych do budowy szybkiego sprawdzania pisowni
Próbuję napisać moduł sprawdzania pisowni, który powinien działać z dość dużym słownikiem. Naprawdę chcę efektywnego sposobu indeksowania danych słownikowych za pomocą odległości Damerau-Levenshteina w celu ustalenia, które słowa są najbliższe błędnie napisanemu słowu. Szukam struktury danych, która dałaby mi najlepszy kompromis między złożonością przestrzeni a złożonością środowiska wykonawczego. Na podstawie …
5
Znajdowanie interesujących anagramów
Powiedzieć, że 1 2 ... n i są dwa ciągi o tej samej długości. Anagramming dwóch ciągów bijective mapowania tak, że dla każdego .a1a2…ana1a2…ana_1a_2\ldots a_nb1b2…bnb1b2…bnb_1b_2\ldots b_np:[1…n]→[1…n]p:[1…n]→[1…n]p:[1\ldots n]\to[1\ldots n]ai=bp(i)ai=bp(i)a_i = b_{p(i)}iii Może być więcej niż jedno anagramowanie dla tej samej pary ciągów. Na przykład, jeśli `abcab` mamy i , między innymi.a=a=a=b=b=b=cababp1[1,2,3,4,5]→[4,5,1,2,3]p1[1,2,3,4,5]→[4,5,1,2,3]p_1[1,2,3,4,5]\to[4,5,1,2,3]p2[1,2,3,4,5]→[2,5,1,4,3]p2[1,2,3,4,5]→[2,5,1,4,3]p_2[1,2,3,4,5] …
1
Czy istnieje struktura danych „ciąg znaków”, która obsługuje te operacje na łańcuchach?
Szukam struktury danych, która przechowuje zestaw ciągów znaków nad zestawem znaków , zdolną do wykonywania następujących operacji. Oznaczmy D ( S ) , jak w strukturze danych przechowującej zestaw łańcuchy S .ΣΣ\SigmaD(S)D(S)\mathcal{D}(S)SSS Add-Prefix-Setna : biorąc pod uwagę pewien zestaw T (prawdopodobnie pustych) ciągów, których rozmiar jest ograniczony stałą, a których …
1
Najdłuższa powtarzająca się (rozproszona) sekwencja w ciągu
Nieformalne oświadczenie o problemie: Biorąc pod uwagę ciąg znaków, np. ACCABBABACCABBABACCABBAB , chcemy pokolorować niektóre litery na czerwono, a niektóre na niebiesko (a niektóre wcale), tak że czytanie tylko czerwonych liter od lewej do prawej daje taki sam wynik jak czytanie tylko niebieskie litery. W przykładzie możemy je pokolorować w …
2
Wydajna struktura danych mapy obsługująca przybliżone wyszukiwanie
Szukam struktury danych, która obsługuje efektywne przybliżone wyszukiwanie kluczy (np. Odległość Levenshteina dla ciągów znaków), zwracając możliwie najbliższe dopasowanie dla klucza wejściowego. Najlepszą strukturą danych, jaką do tej pory znalazłem, są drzewa Burkhard-Keller , ale zastanawiałem się, czy istnieją inne / lepsze struktury danych do tego celu. Edycja: Więcej szczegółów …
1
Kompresja nazw domen
Jestem ciekawy, jak można bardzo kompaktowo skompresować domenę dowolnej nazwy hosta IDN (zgodnie z definicją w RFC5890 ) i podejrzewam, że może to stać się ciekawym wyzwaniem. Host lub nazwa domeny Unicode (etykieta U) składa się z ciągu znaków Unicode, zwykle ograniczonego do jednego języka w zależności od domeny najwyższego …
1
Czy każdy wystarczająco duży ciąg ma powtórzenia?
Niech będzie skończonym zestawem znaków o ustalonym rozmiarze. Niech będzie ciągiem znaków nad . Mówimy, że niepusty substrat z jest powtórzeniem, jeśli dla jakiegoś ciągu .α Σ β αΣΣ\Sigmaαα\alphaΣΣ\Sigmaββ\betaαα\alphaγβ= γγβ=γγ\beta = \gamma \gammaγγ\gamma Teraz moje pytanie dotyczy tego, czy: Dla każdego istnieje pewna liczba taka, że ​​dla każdego łańcucha powyżej …
1
Jak czas działania algorytmu Ukkonen zależy od wielkości alfabetu?
Niepokoi mnie kwestia asymptotycznego czasu działania algorytmu Ukkonena , być może najpopularniejszego algorytmu do konstruowania drzewek sufiksów w czasie liniowym (?). Oto cytat z książki „Algorytmy na strunach, drzewach i sekwencjach” Dana Gusfielda (sekcja 6.5.1): „... wszystkie algorytmy Aho-Corasick, Weiner, Ukkonen i McCreight wymagają albo przestrzeni , albo ograniczenie czasowe …
1
Edytuj odległość listy za pomocą unikalnych elementów
Odległość edycji Levenshtein-Distance między listami jest dobrze zbadanym problemem. Ale nie mogę znaleźć wiele możliwych ulepszeń, jeśli wiadomo, że żaden element nie występuje więcej niż raz na każdej liście . Załóżmy również, że elementy są porównywalne / sortowalne (ale listy do porównania nie są sortowane na początek). O(min(m,n)s)O(min(m,n)s)O(\min(m,n)s)O(min(s,m,n)s)O(min(s,m,n)s)O(\min(s,m,n)s)sss Bardziej formalnie, …
2
Porównanie algorytmu Aho-Corasicka z algorytmem Rabina-Karpa
Pracuję nad algorytmami wyszukiwania ciągów, które obsługują wyszukiwanie wielu wzorców. Znalazłem dwa algorytmy, które wydają się najsilniejszymi kandydatami pod względem czasu działania, a mianowicie Aho-Corasick i Rabin-Karp . Nie udało mi się jednak znaleźć kompleksowego porównania między dwoma algorytmami. Który algorytm jest bardziej wydajny? Który z nich jest bardziej odpowiedni …
5
Częstotliwość wyrazów z uporządkowaniem w złożoności O (n)
Podczas wywiadu na stanowisko programisty Java zapytano mnie: Napisz funkcję, która przyjmuje dwa parametry: ciąg znaków reprezentujący dokument tekstowy i liczba całkowita podająca liczbę elementów do zwrócenia. Zaimplementuj funkcję tak, aby zwracała listę ciągów uporządkowanych według częstotliwości słów, najczęściej występujących jako pierwsze słowo. Twoje rozwiązanie powinno działać w czasie gdzie …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.