Hej,
mam taką przykładową listę list słów:
[['rowerowy', 'rower']
['rowerzysta', 'rower']
['domeczek', 'domek']
['domek', 'dom']
['rowerzystka', 'rowerzysta']]
i potrzebuję złączyć wyrazy w grupy zależności, czyli robimy graf połączeń między formami:
rowerowy --> rower <-- rowerzysta <--- rowerzystka
domeczek --> domek --> dom
Jak zostaną nie podpięte do żadnego grafu pary w relacji to one tworzą graf z jedną krawędzią.
Jakieś pomysły ?
Ja bym tak spróbował, żeby przechodząc po każdej parze stworzyć ten graf.
graf mógłby być słownikiem indeksowanym po słowie (np. rower)
jego węzły mogłyby być słownikami z kluczem name (np. rower) oraz kluczem links, gdzie byłaby lista połączeń do innych węzłów
graf mógłbyś stworzyć tak:
dla każdej pary A-B:
sprawdź, czy węzeł dla nazwy A istnieje, jeśli nie istnieje to stwórz go
sprawdź, czy węzeł dla nazwy B istnieje, jeśli nie istnieje to stwórz go
dodaj węzeł A do B['links']
dodaj węzeł B do A['links']
czy to, co mówię, ma sens?
A dlaczego rowerzystka połączona do rowerzysta a nie do rower? Podobnie domeczek do domek a nie do dom? Nie widzę tu jakiejś wyraźnej reguły. Chyba że te grupy mają znaczenie? Ty sam tworzysz te pary czy to masz jakieś gotowe skądś?
Edit:
Pamiętam, że do grafów była w Pythonie taka biblioteka NetworkX. Nie pamiętam już co ona tam dokładnie robiła, ale może zerkniesz sobie na nią.
Prawa to derywat, lewa to baza derywacyjna.
Relacje zawsze idą OD DERYWATU DO BAZY.
rowerzysta <--- rowerzystka czemu nie rower <--- rowerzystka?
rowerzystka pochodzi od słowa rowerzysta, a nie rower :-P imo to nie jest żadna tajemnica i książki poruszające tę tematykę (np. Feminatywum w uwikłaniach językowo-kulturowych, o ile dobrze jeszcze pamiętam zawartość) też w taki sposób opisywały odmianę (w szczególności sposób w jaki formant -ka jest, uhm, overloaded w języku polskim).
zaraz cię feministki za coś tam powieszą brzmi zwyczajnie jak próba dowalenia grupie osób, zupełnie bez ładu i składu wrzucając politykę do pełni neutralnego wątku 🙃
Na czym polega problem skoro masz juz pary wierzcholkow, na zbudowanie grafu?
Prostym sposobem jest zamenieniem tej listy na slownik:
lista = [
['rowerowy', 'rower'],
['rowerzysta', 'rower'],
['domeczek', 'domek'],
['domek', 'dom'],
['rowerzystka', 'rowerzysta'],
]
graf = {}
for para in lista:
if para[1] not in graf:
graf[para[1]] = ""
graf[para[0]] = para[1]
print(graf)
print()
print(graf[graf["domeczek"]])
wyjscie:
{'rower': '',
'rowerowy': 'rower',
'rowerzysta': 'rower',
'domek': 'dom',
'domeczek': 'domek',
'dom': '',
'rowerzystka': 'rowerzysta'}
dom
Do czego potrzebujesz tego grafu:
Kolejka na bazarku po ogórki.
-Co Pani podać?
-Poproszę ten grubszy.
-Proszę. A Pani co podać?
-Poproszę ten dłuższy.
-Proszę. A Panu co podać?
-A mi wszystko jedno, mi na sałatkę.
_13th_Dragon napisał(a):
Do czego potrzebujesz tego grafu:
- Wyświetlenia?
- Szukania ścieżek?
- Inne zabawy ...?
Na razie muszę to wypisać.
Potem lengwiści z tym pracują.
Suchy702 napisał(a):
ale samo wypisanie moze byc problematyczne, gdy ten graf bedzie bardziej zlozony np taki graf
ab a
ac a
ad a
al a
ala al
all alto wypisanie go to bedzie jakies:
<- ab <- ac a <- ad ala <- al <- all
Nie musi go graficznie wypisać.
Może wypisać listę node'ów (czyli dla grafu który ma 15 node'ów, byłoby 15 linijek), i przy niej wszystkie sąsiednie node'y.
Suchy702 napisał(a):
ale samo wypisanie moze byc problematyczne, gdy ten graf bedzie bardziej zlozony np taki graf
ab a
ac a
ad a
al a
ala al
all al
Ja wypisałbym to następująco (przy dobrej strukturze da się rekurencyjnie):
<- a
<- ad
<- ab
<- ac
<- al
<- ala
<- all
source = \
[
['rowerowy','rower'],
['rowerzysta','rower'],
['domeczek','domek'],
['domek','dom'],
['rowerzystka','rowerzysta'],
]
def showtree(graph,node=None,deep=0):
print(("\t"*deep+"<= " if deep else '')+str(node))
deep+=1
if node in graph:
for sub in sorted(graph[node]):
showtree(graph,sub,deep)
def showtreenoroot(graph,node=None,deep=0):
for sub in sorted(graph[node]):
print(("\t"*deep+"<= " if deep else '')+sub)
if sub in graph:
showtreenoroot(graph,sub,deep+1)
def maketree(source):
graph={}
for pair in source:
nodein,nodeout=pair
if nodeout in graph:
graph[nodeout].add(nodein)
else:
graph[nodeout]={nodein}
graph[None]=set(graph.keys()).difference(set.union(*graph.values()))
return graph
showtree(maketree(source))
print()
showtreenoroot(maketree(source))
print()
showtreenoroot(maketree([['ab','a'],['ac','a'],['ad','a'],['al','a'],['ala','al'],['all','al']]))
Wygląda ok ale przy dużych plikach wywale mi, że za dużo rekurencji :(
Może da się prościej:
ab -> a <- ab <- ac
Sepulka –> Sepulkaria, Sepulkaria -> Sepulenie, Sepulenie -> Sepulka czyli nie jest tak jak mówiłeś na początku.
Paweł Tometczak napisał(a):
Wygląda ok ale przy dużych plikach wywale mi, że za dużo rekurencji :(
Może da się prościej:
ab -> a <- ab <- ac
Czym tobie przeszkadza rekurencja?
Wszystkie przedstawione algorytmy mają złożoność O(1) - tego nie przeskoczysz.
a jeszcze dopytam :-)
mam słownik:
{'odsłuch': ['odsłuchiwać'],
'zgoda': ['zgodzić się', 'zgodzić się', 'godzić'],
'rzeczywisty': ['rzeczywistość', 'rzeczywistość'],
'niezależność': ['niezależny', 'niezależny', 'niezależny'],
'niezależny': ['niezależność', 'niezależność', 'niezależność'],
'mineralny': ['minerał', 'minerał'],
'pociotek': ['pociot'],
'smutny': ['smutek', 'smuta'],
'czerniowiecki': ['Czerniowce'],
'lugrowy': ['lugier'],
'obojętność': ['obojętny', 'obojętny', 'obojętny'],
'szmer': ['szemrać', 'szemrać'],
'akuszerka': ['akuszer', 'akuszerstwo', 'akuszeria']}
Jak najsensowniej wywalić duplikaty z list, które są wartościami słownika ?
set() coś nie idzie:-(
Paweł Tometczak napisał(a):
a jeszcze dopytam :-)
mam słownik:
{'odsłuch': ['odsłuchiwać'], 'zgoda': ['zgodzić się', 'zgodzić się', 'godzić'], 'rzeczywisty': ['rzeczywistość', 'rzeczywistość'], 'niezależność': ['niezależny', 'niezależny', 'niezależny'], 'niezależny': ['niezależność', 'niezależność', 'niezależność'], 'mineralny': ['minerał', 'minerał'], 'pociotek': ['pociot'], 'smutny': ['smutek', 'smuta'], 'czerniowiecki': ['Czerniowce'], 'lugrowy': ['lugier'], 'obojętność': ['obojętny', 'obojętny', 'obojętny'], 'szmer': ['szemrać', 'szemrać'], 'akuszerka': ['akuszer', 'akuszerstwo', 'akuszeria']}Jak najsensowniej wywalić duplikaty w list, które są wartościami słownika ?
set()coś nie idzie:-(
Jeśli słownik jest w zmiennej my_dict, to:
without_duplicates = {key: list(set(value)) for key, value in my_dict.items()}
set() usuwa duplikaty. list() jest po to żeby wynikowa kolekcja miała list, a nie zbiory, tak jak napisałeś wyżej.
data = []
with open('extracted_plwn_deriv.tsv') as file:
for line in file.readlines():
if line not in ['\n']:
if not 'GERUNDIUM' in line:
line = line.strip("\n")
a,b,c = line.split("\t")
data.append([c,a])
out. skrócony:
[['odsłuchiwać', 'odsłuch'],
['zgodzić się', 'zgoda'],
['rzeczywistość', 'rzeczywisty'],
['niezależny', 'niezależność'],
['niezależność', 'niezależny'],
['minerał', 'mineralny'],
['pociot', 'pociotek'],
['smutek', 'smutny'],
['Czerniowce', 'czerniowiecki'],
i dalej
graph_group={}
for pair in data:
nodein,nodeout = pair
if nodeout in graph_group:
graph_group[nodeout].append(nodein)
else:
graph_group[nodeout] = [nodein]
graph_group
out:
{'odsłuch': ['odsłuchiwać'],
'zgoda': ['zgodzić się', 'zgodzić się', 'godzić'],
'rzeczywisty': ['rzeczywistość', 'rzeczywistość'],
'niezależność': ['niezależny', 'niezależny', 'niezależny'],
'niezależny': ['niezależność', 'niezależność', 'niezależność'],
'mineralny': ['minerał', 'minerał'],
'pociotek': ['pociot'],
'smutny': ['smutek', 'smuta'],
'czerniowiecki': ['Czerniowce'],
'lugrowy': ['lugier'],
'obojętność': ['obojętny', 'obojętny', 'obojętny'],...
i po usunięciu duplikatów z list
without_duplicates = {key: list(set(value)) for key, value in graph_group.items()}
without_duplicates
out:
{'odsłuch': ['odsłuchiwać'],
'zgoda': ['godzić', 'zgodzić się'],
'rzeczywisty': ['rzeczywistość'],
'niezależność': ['niezależny'],
'niezależny': ['niezależność'],
'mineralny': ['minerał'],
'pociotek': ['pociot'],
'smutny': ['smuta', 'smutek'],
'czerniowiecki': ['Czerniowce'],
'lugrowy': ['lugier'],
'obojętność': ['obojętny'],...
graph_group={}
for pair in data:
nodein,nodeout = pair
if nodeout in graph_group:
graph_group[nodeout].add(nodein) # zmiana 1
else:
graph_group[nodeout] = {nodein} # zmiana 2
graph_group
graph_group = {key: list(value) for key, value in graph_group.items()}
Zarejestruj się i dołącz do największej społeczności programistów w Polsce.
Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.