Taoffi's blog

prisonniers du temps

doc5ync Trie integration tool - UI Tag cloud, paging and navigation

The integration client tool I talked about in the previous post, we need to display the list of words in a way similar to tag clouds in blog post.

For this we will use a ListView with some customization (see Xaml code below).

Paging

A more important question is the number of items to show. As we, in most cases, have thousands of items to display, we need a paging mechanism.

A solution – a Linq extension - proposed by https://stackoverflow.com/users/69313/wim-haanstra was a good base for a generic paging module:

 

// credit: https://stackoverflow.com/users/69313/wim-haanstra
// usage: MyQuery.Page(pageNumber, pageSize)
public static class LinqPaging
{
    // used by LINQ to SQL
    public static IQueryable<TSource> Page<TSource>(this IQueryable<TSource> source, int page, int pageSize)
    {
        return source.Skip((page - 1) * pageSize).Take(pageSize);
    }

    // used by LINQ
    public static IEnumerable<TSource> Page<TSource>(this IEnumerable<TSource> source, int page, int pageSize)
    {
        return source.Skip((page - 1) * pageSize).Take(pageSize);
    }

}

trie-with-data-paging-base

iObjectPaging is now a generic class accepting any collection of data to be paged through calls to the Linq extension.

Let us derive, from this base, a two specific paging classes: one for our words and another for our documents (DataItems):

trie-with-data-paging-2

That is all what we need for paging. Each list will simply assign its data to the corresponding paging object and the UI elements will be bound to the CurrentPageData collection. Next / Previous buttons will allow navigating through the collection pages.

The main view model, for instance, declares a paging member:

protected iWordPaging	_wordPaging	= new iWordPaging(200);

And assigns its Words collection to this paging member whenever the collection changes:

_wordPaging.SourceCollection	= ItemList?.AllWords;

 

Words as Tag Cloud

A ListView control should be customized for this.

We need to customize its ItemsPanel and ItemTemplate:

<ListView x:Name="listItems" 
			Grid.Row="1" 
			ItemsSource="{Binding WordPaging.CurrentPageData, IsAsync=True}" 
			BorderBrush="#FFA3A3A4" BorderThickness="1"
			SelectedItem="{Binding SelectedWord, Mode=TwoWay, IsAsync=True}" Background="{x:Null}"
			Padding="12" ScrollViewer.HorizontalScrollBarVisibility="Disabled"
			>
   <ListBox.ItemsPanel>
       <ItemsPanelTemplate>
          <WrapPanel MaxWidth="{Binding ElementName=listItems, Path=ActualWidth, Converter={StaticResource widthConverter}}" HorizontalAlignment="Left" Height="auto" Margin="12,0,12,0" />
       </ItemsPanelTemplate>
   </ListBox.ItemsPanel>

   <ListView.ItemTemplate>
       <DataTemplate>
          <local:iWordCtrl DataContext="{Binding }" Width="120" Height="40" />
       </DataTemplate>
    </ListView.ItemTemplate>
  </ListView>
 

Data items grid

A DataGrid bound to the selected Word data items will display its (paged) data items:

<DataGrid ItemsSource="{Binding CurrentPageData, IsAsync=True}">
   <DataGrid.Columns>
    …
    …


 

With this in place, we are now able to:

  • Navigate though word pages
  • When the selected word changes, its related data (paged) items (e-books) are displayed in the DataGrid…
  • Next / Previous buttons can be used to navigate, and will be enabled or disabled according to the paging context (see paging base class in the diagram above)
  • A list of pages (combo box) can also allow to go to a specific page

 

trie-with-data-paged-word-cloud

 

Sample paged datagrid of e-books containing the selected word

trie-with-data-paged-datagrid

In a next post, we will see the database integration process

doc5ync Trie index integration tool

That is a maintenance WPF client application for indexing words found in e-book titles and descriptions for the doc5ync project. (http://doc5.5ync.net/)

Before talking about technical details, let us start by some significant screenshots of the app.

1. scanning All languages’ words for 10000 data records with minimum words length of 4 chars.

trie-with-data-window1

After the scan, words are displayed (on the left side of the above figure) highlighting the occurrences of each word (greater font size = more occurrences). This done using a user control itself using a converter.

trie-with-data-word-control

A simple Border enclosing a TextBlock

<UserControl.Resources>
	<conv:TrieWordFontSizeConverter x:Key="fontSizeConverter" />
</UserControl.Resources>
<Grid x:Name="grid_main">
	<Border BorderBrush="DarkGray" CornerRadius="2" Background="#FFEDF0ED" Height="auto" Margin="2" BorderThickness="1">
		<TextBlock Text="{Binding Word}"
					Padding="4px"
					VerticalAlignment="Center"
					HorizontalAlignment="Center"
					FontSize="{Binding ., Converter={StaticResource fontSizeConverter}, FallbackValue=12}"
					>
		</TextBlock>
	</Border>

	</Grid>
 
 
The converter emphasizes the font size relative to the word’s occurrences:
 
public class TrieWordFontSizeConverter : IValueConverter
{
    public object Convert(object value, Type targetType, object parameter, CultureInfo culture)
    {
        double minFontSize = 11.0,
              defaultFontSize = 12.0,
              maxFontSize = 32.0,
              size;
         if (System.ComponentModel.DesignerProperties.GetIsInDesignMode(new DependencyObject()))
            return defaultFontSize;

         double min = (double) iWordsCentral.Instance.MinOccurrences,
                max = (double) iWordsCentral.Instance.MaxOccurrences;
         iTrieWord word = value as iTrieWord;

         if( word == null)
            return defaultFontSize;

         max = Math.Min(9, max);
        size = (word.Occurrences / max) * maxFontSize;

        if(size > maxFontSize)
            return maxFontSize;
        if(size < minFontSize)
            return minFontSize;
        return size;
}

Load, Scan and link words to data items

The View Model objects and processing flow

trie-with-data-view-model

iWordsCentral is the ‘main’ view model (singleton) which provide word scanning and data object assignment through its ScanWordsData (iData object)

ItemList (iDataItemList) is iData’s member responsible for building the Trie (its member) and assigning Trie’s words to its data items.

On Load button click, the MainWindow calls its LoadData() method.

 
async void ReloadData()
{
	await Task.Run(() => iWordsCentral.Instance.LoadData());
}
 

The method loads data records into (the desired number of records is a parameter… see main figure) and assign it to the ItemsList of the scan object (iData), then calls the iData’s method to build the Trie and assign data items to each of the Trie’s nodes.

 

_scanWordsData.ItemList	= rootList;

bool scanWordsResult = await _scanWordsData.ScanDataWordsAsync(_minWordLength, _includeDocAreaWords, _cancelSource.Token);

 

The iData object calls its ItemList to do the job… its method proceeds as in the following code

public async Task<bool> ScanDataWordsAsyn(int minWordLength, bool scanRootItems, CancellationToken cancelToken)
{
    if(_trie == null)
        _trie = new iTrie();

    // build a single string with all textual items and parse its words
	iTrie		trie			= _trie;
	string		global_string	= "";

        foreach( iDataItem item in this)
        global_string	+= item.StringToParse;
        await Task.Run(() => _trie.LoadFromStringAsync(global_string, minWordLength, notifyChanges: false));

        _trie.Sort();
        List<iTrieWord>	trieWordList	= trie.AllStrings;

        // copy the Trie words (strings) to a DataTrieWord list
	CopyDataWords(trieWordList);

        // assign words to data items
        bool result = await AssignTrieWordsDataAsync(scanRootItems, cancelToken);
	return result;
}


 

The data Item List loops through all its words and data items, calling each data item to assign itself to the given word if it is contained in its data

foreach (var word in _dataWordList)
{
   foreach (var ditem in this)
      await ditem.AssignChildrenTrieWordAsyn(scanRootItems, word, cancelToken);
}

The data item looks for any of its data where a match of the given word is found and assign those items to the word:

var wordItems	= this.Children.Where( i => i.Description != null 

				&& i.Description.IndexOfWholeWord( word.Word) >= 0);

IndexOfWoleWord note

That is (an efficient) string extension which is important to ensure that one whole word is present in data. I struggled to find a solution for this question, and finally found an awesome solution proposed by https://stackoverflow.com/users/337327/palota

 

// credit: https://stackoverflow.com/users/337327/palota
public static int IndexOfWholeWord(this string str, string word)
{
    for (int j = 0; j < str.Length && 
        (j = str.IndexOf(word, j, StringComparison.Ordinal)) >= 0; j++)
        if ((j == 0 || !char.IsLetterOrDigit(str, j - 1)) && 
            (j + word.Length == str.Length || !char.IsLetterOrDigit(str, j + word.Length)))
            return j;
    return -1;
}
 

Finally, as you may have noticed, for performance measurement, a simple StopWatch is embedded into the main view model to notify elapsed time during the process. For this to have sense, all methods are of course async notifying changes through the UI thread (Dispatcher). You might ignore all the async artifacts in the above code to better concentrate on the processing steps themselves.

Presentation

Once all the processing is done, there is still the presentation UI work to do in order to display the document list of a selected word.

This will be the subject of a next post.

 

doc5ync – the Trie in practice for online e-books

I spent the past few months working on a new web project referencing online e-books (http://doc5.5ync.net/)

The goal of the project was not to build a new online library (many good libraries are already out there) but rather to offer a central reference for all what exists, adding some features for these references to provide a new analytical view of e-books.

Most of online libraries offer access to books that are now in the ‘public domain’ (I.e. no more copyright protected) and thus available for free download.

For an analytical approach, I started to use the Trie structure (I talked about this in a previous post) for analyzing textual elements of the referenced e-books to provide relational aspects among them.

Just a reminder, explained in the previous post: a Trie is a tree-like structure where a node has a parent, neighbors and descendants. The structure is particularly interesting for text indexing because, whatever the language, any textual unit (word) is forcibly composed of a set of that language’s alphabet (whose number is quite limited). Adding a flag to end-of-word nodes, we can build a Trie whose root is composed of the few units of the alphabet with branches to text words.

trie-word-nodes

This compact structure enables fast and efficient search and retrieve elements into large text sequences. Which seems to be a good base for our e-book text indexing and analysis.

Using the trie structure to index e-book details (titles, description, author…) of the relatively large number of referenced e-books (approx. 9000 as of writing) was straightforward and efficient.

Now, a given unit (word) in this trie might be related to one or more of our e-books. How to link our trie nodes each to its set of ‘data’? That is the subject of this brief post.

We are going to build upon the elements mentioned in in the previous post:

  • We will use our Trie with its (char) Dictionary and Nodes.
  • Our trie provides us with its words presented as a collection of iTrieWord objects
  • Let us create a new object iTrieDataWord (deriving from iTrieWord)
  • This last object will contain a collection of ‘Data items’ (in our concrete case, this will be a collection of e-books)

trie-with-data

How to proceed?

After some experimentations Smile, I ended up using the following steps which seemed to be good in regards of efficiency and performance:

  • Load all e-books’ textual sequences (titles, descriptions, author information… for the time being)
  • Build the Trie of this text sequences (more about this later)… which provides us with its Words (iTrieWord) collection
  • Now, in the loaded collection of e-book records (the iDataItem(s)). (Each record contains the e-book title, description and author information)… each record (iDataItem) can assign itself to any of the Trie words whenever that word is part of its own data.

Some additional considerations in the process are quite important:

    • One important point is to define “What is a ‘Word’”?  in terms of minimum number of characters to consider a sequence as a ‘word’. As the referenced e-books are multilingual, it was somehow clear that this threshold is language-dependent. In Arabic, for instance, words tend to be short in terms of number of characters (Arabic vowels are often part of the character). After some research, I found that considering 4 chars as a minimum is an acceptable compromise as it allows searching the e-books by year (author’s or book’s) which may be quite useful.
    • It is also important to define what are ‘word-delimiters’ (spaces are not the only ones to consider!). Actually, that is also language-dependent in some ways… and as such requires experimentations with all languages to be used in the given project.
    • Finally: what are we going to do for all this to b useful?... I.e. Are we going to persist this Trie? Or rather proceed as a (runtime queryable) indexing service?… etc. For doc5 project, we decided to persist the results in data tables / running the scan process periodically

Some performance numbers

Some numbers to justify using the above steps:

  • Reading data records + Building a Trie of 40365 words (min = 4 chars): 17s
  • Processing 9000 e-book information (I.e. building the Trie + creating 358000 links to its words): 8min30s

Will post some sample code in the coming weeks. You may have a look at http://doc5.5ync.net/ (The current version for presenting the results).

A bit late!: Wish you all a happy 2020 year, with many useful projects and much fun!